Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

 Dit is een reactie op vraag 60498 

Re: Modulusrekenen

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·n25-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: n25=37 (of -37) (mod 83).

Je kan in jouw voorbeeld n25 berekenen door eerst n5 te vereenvoudigen en dan die uitkomst weer tot de macht 5 te verheffen.
Het kan natuurlijk ook direct :n25, 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 n5, 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: n5=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. 25 en 35 hebt berekend, gebruiken dat geldt: 65=25·35 (mod 83). Soms is dat sneller.
Zou het zo lukken?
Groeten,
Lieke.

ldr
zondag 18 oktober 2009

©2001-2024 WisFaq