WisFaq!

Re: Modulusrekenen

Dag Lieke,

ik ken van modulo rekenen niet veel. Je zal me nog wat moeten voortduwen, vrees ik.
...
Groeten

Rik Lemmens
17-10-2009

Antwoord

Beste Rik,
We rekenen modulus 83, d.w.z. dat we kijken naar de rest na deling door 83.
Alle getallen zijn te vereenvoudigen tot een getal van 0 t/m 82, of b.v. van -41 t/m 42.
Belangrijk zijn de rekenregels.
Je kan bewijzen dat de bewerkingen optellen/aftrekken en vermenigvuldigen (niet delen) ook modulus m gelden.
Dus b.v. 8 +7·9 (mod 5)=3+2·4=9=4
Zie o.a.:http://www.win.tue.nl/~jessers/aansluiting/rekenenmetresten.htm
of http://nl.wikipedia.org/wiki/Modulair_rekenen

Als 7·n²⁵-10=0 (mod 83), dan weten we dat het linker lid deelbaar is door 83.
De oplossing van 7k-10=0 (mod 83) kan je ook schrijven als:
7k-m·83=10. Dit is een diofantische vergelijking, op te lossen met het algoritme van Euclides. Uitkomst: k=37 (m=3).
We zoeken dus naar een getal n waarvoor geldt: n²⁵=37 (of -37) (mod 83).

Je kan in jouw voorbeeld n²⁵ berekenen door eerst n⁵ te vereenvoudigen en dan die uitkomst weer tot de macht 5 te verheffen.
Het kan natuurlijk ook direct :n²⁵, maar daar komen gauw te grote getallen uit voor een eenvoudige rekenmachine.

Je zou nu een lijstje kunnen maken met de uitkomsten modulo 83 van n⁵, voor n=1 t/m 82. Of: voor n=-41 t/m 42, dat scheelt al de helft.
Zodra je een uitkomst 37 of -37=83-37=46 vindt (zeg p) ga je zoeken naar een getal n waarvoor geldt: n⁵=p of 83-p.
Het zal blijken dat je maar t/m n=16 hoeft te gaan, dus dat valt nog wel mee.
Ook mag je als je b.v. 2⁵ en 3⁵ hebt berekend, gebruiken dat geldt: 6⁵=2⁵·3⁵ (mod 83). Soms is dat sneller.
Zou het zo lukken?
Groeten,
Lieke.

ldr
18-10-2009