WisFaq!

Modulo rekenen

Ik zit met een probleem betreffende de inverse restklasse van een modulus. We weten dat wanneer GGD(a,b)=1, dan is er een X en een Y waarvoor geldt: xa + yb = 1

Als voorbeeld:

Zoek de inverse restklasse van 341(mod5144)
Via het algoritme van Euclides komen we uit op
-47x5144 + 709x341 = 1, dus 709 is de inverse restklasse van 341 mod 5144.

Nu stuitte ik op een ander voorbeeld waarvan ik niet helemaal begreep hoe ze aan het antwoord kwamen:

Wat is de inverse restklasse van 19 mod 32
Via het algoritme van Euclides kom ik op 5x32-5x19=1
Omdat eigenlijk de vraag ook is: zoek een a waarvoor geldt
19a=1 mod32 zou je verwachten dat het antwoord -5 is.

Echter het antwoord is 27! Hoe ze aan het getal komen? Ik kan alleen maar raden dat 32-5=27, maar daarmee begrijp ik het antwoord nog niet. Wie kan mij helpen?

Willem van Bentum
4-3-2009

Antwoord

Eerst de ggd van 19 en 32 berekenen

32 = 1 · 19 + 13 Þ 13 = 32 - 1 · 19
19 = 1 · 13 + 6 Þ 6 = 19 - 1 · 13
13 = 2 · 6 + 1 Þ 1 = 13 - 2 · 6

Nu terug rekenen

1 = 13 - 2 · 6
1 = 1 · 13 - 2 · (19 - 1 · 13)
1 = 3 · 13 - 2 · 19
1 = -2 · 19 + 3 · (32 - 1 · 19)
1 = -5 · 19 + 3 · 32

de inverse van 19 (mod 32) is -5 (mod 32)
de inverse van 19 (mod 32) is 27

Zie Bereken de inverse van a (mod b)

Maar -5 is modulo 32 hetzelfde als 27?

Z₂₇={..., -69, -37, -5, 27, 59, 91, ...}

WvR
5-3-2009