WisFaq!

Re: Inverse van 301 (modulo 577)

Het vinden van de grootste gemene deler lukt me nog wel, maar van de tweede stap zie ik niet wat er gedaan wordt. Het algoritme van Euclides lijkt er ook toegepast te worden, maar hoe?

Arnie
16-12-2006

Antwoord

De inverse van 301 (mod 577) is een getal m zo, dat m·301=1 (mod 577).
Merk op dat dit niet één getal is maar een restklasse modulo 577. (dus als m·301=1 mod 577, dan is m+k·577, met k geheel) dat ook.)

Uit de berekening blijkt dat 1=-23·301+12·577.
Omdat 12·577=0 mod 577 weten we nu dat -23·301=1 (mod 577).
We kiezen nu het getal -23+577=554 als representant van de restklasse.

hk
17-12-2006