WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Re: Modulusrekenen

Dit is een reactie op vraag 60498

Dag Lieke,

ik ken van modulo rekenen niet veel. Je zal me nog wat moeten voortduwen, vrees ik.
...
Groeten
Rik Le
Iets anders - zaterdag 17 oktober 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

Vragen naar aanleiding van dit antwoord? Klik rechts..!
zondag 18 oktober 2009