De kleine stelling van Fermat zegt dat als \(p\) een priemgetal is en \(a\) niet deelbaar is door \(p\), dan is de rest van \(a^{p-1}\) bij deling door \(p\) exact gelijk aan 1. We kunnen dit gebruiken om een algoritme te ontwikkelen dat efficiënt kan testen of een getal priem is of niet. Hiervoor lopen we alle getallen \(a\) af tussen 1 en \(n-1\) (dus \(1 < a < n-1\)). Als we voor alle geteste waarden van \(a\) uitkomen dat \(a^{n-1}\) rest 1 geeft bij deling door \(n\), dan is \(n\) waarschijnlijk een priemgetal. Als er ook maar één waarde voor \(a\) is waarvoor deze eigenschap niet geldt, dan is \(n\) zeker geen priemgetal.
We spreken van waarschijnlijk priem ipv zeker priem omdat de priemtest van Fermat soms een fout antwoord kan geven:
Dit komt doordat er getallen \(n\) bestaan die niet priem zijn maar die voor elke \(1 < a < n-1\) wel rest 1 geven als je \(a^{n-1}\) deelt door \(n\). Dit zijn de zogenaamde Carmichaelgetallen. Die getallen zijn zeldzaam, maar ze bestaan: het kleinste Carmichaelgetal is 561.
Schrijf een programma dat via de priemtest van Fermat nagaat of een gegeven getal waarschijnlijk priem is of zeker niet priem is. Als het getal waarschijnlijk priem is, geef dan True terug; geef anders False terug.
Invoer:
3
Uitvoer:
True