\require{AMSmath}

Dit is een reactie op vraag 69554

Re: Miller Rabin test

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.

hk
maandag 14 januari 2013

©2001-2024 WisFaq