Re: Miller Rabin test
U beweert (29-1)2 (mod 29)=1
en (643-1)2 (mod 643) =1
Oftewel: (N-1)2 (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)2 mod n=a2 mod n.
Dat is nu niet direct een stelling, maar kan eenvoudig worden bewezen door de haakjes uit te werken.
Immers: (n-a)2=n2-2an+a2.
aangezien n2 , 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.
maandag 14 januari 2013
©2001-2024 WisFaq
|
Dit is een reactie op vraag 69554