Re: Inverse van 301 (modulo 577)

Dit is een reactie op vraag 2475

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
Leerling bovenbouw havo-vwo - zaterdag 16 december 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.

zondag 17 december 2006

©2001-2024 WisFaq