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.