Priemgetallen

Is er een soort formule om priemgetallen in een getallenreeks snel op te sporen ?

Patric
Student Hoger Onderwijs België - vrijdag 24 oktober 2003

Antwoord

Hoi,

Voor sommige getallenreeksen zal dit eenvoudig zijn. Als je bijvoorbeeld hebt: u₁=p met p priem en u_n=u_n-1·2, dan zal enkel u₁ priem zijn. In het algemeen zal het van de getallenreeks afhangen of je al dan niet (makkelijk) kan bepalen welke termen priem zijn. Nog algemener is de vraag hoe je bepaalt of een getal priem is. En dan wordt het helemaal interessant.

We veronderstellen dat n een natuurlijk getal is en we willen bepalen of n priem is.

Eén test bestaat erin alle getallen d tussen 1 en n te overlopen en te onderzoeken of d een deler is van n. Is dit zo, dan is n niet priem, anders wel. Praktisch volstaat het priemgetallen $<$ √n te overlopen.

Een andere (niet zo praktische) test is gebaseerd op de stelling van Wilson. Een getal n is priem als en slechts als (n-1)!=-1 (mod n).

Nog een andere test is gebaseerd op de kleine stelling van Fermat: als n priem is, dan is aⁿ=a (mod n) voor elke a met ggd(a,n)=1. Als je dus een getal a vindt, zodat aⁿ$\ne$a (mod n), dan is n NIET priem. Dit is eerder een snelle vertrouwenstest, want je kan eigenlijk niet bewijzen dat n wel priem is, als je zo geen a vindt... Praktisch kan je heel snel en betrouwbaar een eerste schifting doorvoeren door 2ⁿ=2 (mod n) na te gaan. Als dit niet klopt, is n niet priem. Als dit wel klopt, probeer je 3,5,7,11,13,17,... in de plaats van 2.
De kans dat n niet priem is, terwijl een (beperkt) aantal van die testen wel kloppen, is kleiner dan de kans dat je pc een rekenfout maakt... (te bewijzen )
Bemerk dat je (met een pc) heel snel en efficiënt modulaire machten kan bereken door a, a²,a⁴,a⁸, ... 'gepast' samen te stellen.

Groetjes,
Johan

andros
vrijdag 24 oktober 2003

©2001-2024 WisFaq