WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Re: Miller Rabin test

Dit is een reactie op vraag 69554

U beweert (29-1)² (mod 29)=1
en (643-1)² (mod 643) =1
Oftewel: (N-1)² (mod N) = 1
Ik herken deze stelling niet. Heeft het met de stelling van Euler te maken?
herman
Leerling bovenbouw havo-vwo - maandag 14 januari 2013

Antwoord

Voor iedere n geldt (n-a)² mod n=a² mod n.
Dat is nu niet direct een stelling, maar kan eenvoudig worden bewezen door de haakjes uit te werken.
Immers: (n-a)²=n²-2an+a².
aangezien n² , zowel als 2an deelbaar zijn door n, volgt het gestelde.
In dit geval is a=1.
Noem dit maar de stelling van hk, als je perse een stelling wilt gebruiken.
Dus vanaf heden heet dit de stelling van hk.

Vragen naar aanleiding van dit antwoord? Klik rechts..!
maandag 14 januari 2013