WisFaq!

Inverse van a modulo n berekenen

Hoe bereken ik bijvoorbeeld de som 2^-1 % 17.
Ik weet dat er 9 uit moet komen want (2·9) % 17 = 1.
Maar, hoe berekende je nu ook alweer de modulo op een
rekenmachine. Er was ergens een heel simpel trukje voor,
ik ben het alleen weer vergeten. (Dat berekenen kon nog zonder de 'duurdere' grafische rekenmachine)
MvG

Maarten Koopmans
5-1-2003

Antwoord

Hoe bereken je de inverse van 2 MOD 17?

Eerst de ggd van 2 en 17 berekenen
17 = 8 · 2 + 1 Þ 1 = 17 - 8 · 2

Nu terug rekenen
1 = 17 - 8 · 2

De inverse van 2 (mod 17) is -8 (mod 17)
De inverse van 2 (mod 17) is 9

Met de rekenmachine kan je modulo 17 (bijvoorbeeld) berekenen door een getal eerst te delen door 17, de helen er af te trekken en dan weer te vermenigvuldigen met 17.
Dus:
123551/17$\to$7267,705882...
7267,705882...-7267$\to$0,705882...
0,705882...×17$\to$12
Conclusie: 123551 MOD 17 = 12

Zie Bereken de inverse van a (mod b) [http://www.wiswijzer.nl/pagina.asp?nummer=216]

WvR
5-1-2003