De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  prikbord |  gastenboek |  wie is wie? |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ's
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

Modulus grote integers

Ik wil uitrekenen de modulus van een groot getal:
N=182316110684665468232161 mod 97.
Wat is de snelste oplossing? Ik las ergens:
Neem de eerste 9 cijfers van N mod 97 = r1
Zet deze r1 voor de 2e reeks 9 cijfers van N en mod 97 = r2
Zet deze r2 voor de laatste 5 cijfers van N en mod 97 = antw.
Maar op welke wiskundige theorie is dit gebaseerd waardoor dit werkt?

herman
3de graad ASO - maandag 18 december 2017

Antwoord

Dat is gewoon modulair rekenen: je schrijft je getal van 24 cijfers als
$$
a\cdot10^{15} + b\cdot10^6+c
$$Hier is $a$ het getal gevormd door de eerste negen cijfers, $b$ door de volgende negen cijfers, en $c$ de laatste zes cijfers.
Als $a\equiv r_1 \pmod{97}$ dan geldt ook $a\cdot10^{15}\equiv r_1\cdot10^{15}$ dus als je de eerste zes cijfers vervangt door de twee cijfers van $r_1$ zijn het oude en nieuwe getal equivalent modulo $97$.
De tweede stap kijkt naar
$$
r_1\cdot10^9+b
$$als je daarbij $r_2$ vindt geldt
$$
(r_1\cdot 10^9 +b)\cdot10^6 \equiv r_2\cdot10^6 \pmod{97}
$$en dus geeft vervanging van de cijfers van $r_1$ en $b$ door $r_2$ weer een equivalent getal.

Het idee is wellicht dat modulo rekenen met getallen van negen cijfers wat minder werk is dat in een keer het hele getal te nemen. Je kunt ook kleinere groepjes cijfers nemen (zes cijfers bijvoorbeeld) dat kost meer stappen maar misschien toch wat minder rekenwerk.

kphart
Vragen naar aanleiding van dit antwoord? Klik rechts..!
maandag 18 december 2017
 Re: Modulus grote integers 



klein |  normaal |  groot

home |  vandaag |  bijzonder |  twitter |  gastenboek |  wie is wie? |  colofon

©2001-2021 WisFaq - versie 3