Wyznaczyć modulo

qba_wl · Post autor: **qba_wl** » 31 sty 2010, o 10:47

Czy ktoś potrafi rozwiązać takie zadanie?
Rozstrzygnąć, czy istnieją elementy \(\displaystyle{ 27^{-1} mod 93}\) oraz \(\displaystyle{ 17^{-1} mod 93}\). Jeżeli tak, to wyznaczyć je.
Z góry dziękuje za pomoc.

klaustrofob · Post autor: **klaustrofob** » 31 sty 2010, o 11:50

a) \(\displaystyle{ 27\cdot x\equiv_{93} 1}\) oznacza, że \(\displaystyle{ 27\cdot x-1=93\cdot y}\) dla pewnego y. ale to jest niemożliwe (czemu?)
b) jak wyżej, wystarczy rozwiązać równanie \(\displaystyle{ 17\cdot x-93y=1}\) (które tym razem ma rozwiązanie) czyli \(\displaystyle{ x=\frac{93y+1}{17}}\). podstawiaj kolejno x=0, 1, ..., 16. (podpowiedź: jest to liczba między 0 a 3)

qba_wl · Post autor: **qba_wl** » 31 sty 2010, o 11:53

Dzięki wielkie! Teraz na pewno sobie poradzę -- 31 sty 2010, o 13:40 --Jeszcze mam tylko takie pytanie: czy na końcu nie powinno się podstawiać za y żeby wyszedł dobry wynik? Bo inaczej traci to trochę sens...

Dumel · Post autor: **Dumel** » 31 sty 2010, o 14:04

element odwrotny do \(\displaystyle{ a}\) w arytmetyce modulo \(\displaystyle{ b}\) istnieje wtw a i b są względnie pierwsze.
przy większych liczbach podstawianie po kolei może nie być za fajne więc lepiej wykorzystać rozszerzony algorytm Euklidesa