kongruencje

Gobol · Post autor: **Gobol** » 20 paź 2006, o 09:01

Czy jest jakaś uniwersalna metoda na rozwiązywanie równania typu:
a • x ≡ b (mod c)
Ja sobie wymysliłem taką metodą, że najpierw z rozszerzonego algorytmu euklidesa obliczam odwrotnosc (b mod c) (oznaczmy k) i mnoże początkowe równanie przez tę liczbe i otzymuje
a • k • x ≡ 1 (mod c) i teraz wystarczy policzyć odwrotność (a•k mod c) i wynik gotowy.
Tylko mam jedno pytanie co zrobić gdy nie istnieje odwrotność (b mod c)?

Sir George · Post autor: **Sir George** » 20 paź 2006, o 10:41

Gobol pisze:najpierw (...) obliczam odwrotnosc (b mod c) (oznaczmy k)

Czemu tak skomplikowanie... Nie lepiej od razu obliczyć odwrotność a modulo c? I nie przejmować się istnieniem, czy nieistnieniem odwrotności b?

Gobol · Post autor: **Gobol** » 20 paź 2006, o 13:56

Sorry , ale nie bardzo rozumiem.
Jak oblicze odwrotność a modulo c to co mam z nią dalej zrobić? Bo z tego co rozumiem to to nie jest odpowiedz (byłaby tylko wtedy gdyby b wynosiło 1)

Sir George · Post autor: **Sir George** » 20 paź 2006, o 15:25

Gobol pisze:Jak oblicze odwrotność a modulo c to co mam z nią dalej zrobić?

A pomnożyć tak przez nią obie strony równości..?

(po lewej dostajemy samo x, a po drugiej... rozwiązanie)

Jaan Klaas · Post autor: **Jaan Klaas** » 25 paź 2006, o 14:07

Witam, czy mógłby ktoś mi wytłumaczyć co to jest (definicja + wytłumaczenie na język polski) 'odwrotność a modulo c' czy jakoś tak? I jak się to oblicza?
Z góry dzięki. Pozdrawiam

DEXiu · Post autor: **DEXiu** » 25 paź 2006, o 15:09

Przez odwrotność \(\displaystyle{ a}\) modulo \(\displaystyle{ c}\) rozumiemy taką liczbę \(\displaystyle{ r}\), że \(\displaystyle{ \frac{1}{a}\equiv r\,(mod\,c)}\), to znaczy \(\displaystyle{ a\cdot r\equiv1\,(mod\,c)}\)