] >
Voor ‘kleine’ kunnen we op systematische wijze de priemfactorontbinding vinden door proberen of met behulp van een factortabel. Voor ‘grote’ getallen kunnen we constateren dat ze samengesteld zijn dan wel zeer waarschijnlijk een priemgetal. Wat we nog zouden willen is:
In deze paragraaf wordt een methode van Lucas behandeld waarmee in sommige gevallen bewezen kan worden dat een getal priem is zonder dat geprobeerd wordt het getal te ontbinden. Deze methode is geschikt als van het getal wel een priemfactorontbinding gevonden kan worden. De methode is verder te verfijnen zodat hij ook werkt als van een grote deler van de priemfactorontbinding kan worden gevonden.
Is er een met , dan zijn er minstens elementen in en is dus alleen niet inverteerbaar. Dat betekent dat een priemgetal is. Uit Lemma 11.41 volgt:
Extreme voorbeelden van getallen waarvoor de priemfactorontbinding van geen probleem is, zijn de Fermatgetallen.
13.16 Definitie. Het -de Fermatgetal is het getal . Is een priemgetal, dan heet een Fermatpriemgetal.
Voor t/m zijn dit de getallen , , , en . Dat zijn inderdaad priemgetallen. Fermat dacht dat alle Fermatgetallen priemgetallen zijn. Ongeveer een eeuw na Fermat liet Euler zien dat geen priemgetal is: is er een deler van. Die deler had hij snel gevonden omdat hij begreep dat alleen priemdelers van de vorm bekeken hoeven te worden. Dit volgt uit:
Bewijs. We hebben: . Hieruit volgt dat de orde van in gelijk is aan . Dus: . □
Lucas heeft dit resultaat nog wat aangescherpt:
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
De Fermatgetallen met zijn samengesteld. Voor geen enkele is de priemfactorontbinding van bekend. Wel zijn voor een aantal Fermatgetallen een of meer priemdelers gevonden. Het is onbekend of er nog een Fermatpriemgetal is. Voor gelijk aan en is er geen priemdeler bekend.
Voor het priem zijn van Fermatgetallen is er de test van Pépin. Deze is gebaseerd op:
Bewijs.
Het grootste Fermatgetal waarvoor de test van Pépin is gebruikt is . Van dit getal is geen priemfactor bekend.
De code voor de test van Pépin is eenvoudig:
Met pepin(m) wordt het -de Fermatgetal getest.
Laat een oneven getal zijn dat waarschijnlijk priem is. Kennen we de priemfactorontbinding van , dan kunnen we die gebruiken om te bewijzen dat een priemgetal is. Ook een gedeeltelijke ontbinding van kan worden gebruikt. Daarmee is de -test aan te scherpen. Die versterking van de test is gebaseerd op:
13.20 Stelling (Pocklington). Zij een oneven getal. Verder is gegeven een ontbinding met . Zij met en voor alle priemdelers van . Dan geldt voor iedere priemdeler van dat .
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
13.21 Gevolg. Als in de situatie van Stelling 13.20 bovendien geldt dat , dan is een priemgetal.
Bewijs. Zij een priemdeler van . Dan en dus . Dit geldt voor iedere priemdeler van . Dus is een priemgetal. □
Een -test kan worden gebaseerd op Gevolg 13.21. Hij is nog verder aan te scherpen, maar dat doen we hier niet.
De functie pocklington(n, k, K) bepaalt voor een oneven met een deler van , en waarbij de lijst van priemdelers van is, of priemdelers van congruent modulo zijn.
Het getal is zeer waarschijnlijk een priemgetal. Een factorisatie van is in dit geval snel gevonden en die kan worden gebruikt om aan te tonen dat inderdaad een priemgetal is. Er kunnen meer stappen nodig zijn: