De zeef van Eratosthenes
                met de priemgetallen kleiner dan 120

Vier wetenswaardigheden over priemgetallen.

1 Wat zijn priemgetallen?
Een priemgetal is een natuurlijk getal met twee verschillende delers, nl. 1 en het getal zelf. De priemgetallen zijn dus 2, 3, 5, 7, 11, ....
De naam priemgetal is afgeleid van het Latijnse woord 'primus', wat eerste of primair betekent. Priemgetallen kan men immers de atomen van de getallenleer noemen omdat elk natuurlijk getal groter dan 1 ofwel zelf een priemgetal is, ofwel op een unieke manier te schrijven is als een product van priemgetallen. Zo is bv. 180 = 2 . 2 . 3 . 3 . 5 = 2² . 3² . 5  en  2009 = 7 . 7 . 41  = 7² . 41. Men zegt dan dat 7 en 41 priemdelers zijn van 2009.

2 Zijn er oneindig veel priemgetallen?
Ja!
Dit is reeds in de 3de eeuw v. Chr. bewezen door Euclides. Hij gebruikte hiervoor een bewijs uit het ongerijmde.
Veronderstel immers dat het aantal priemgetallen eindig is en dat p het grootste priemgetal is. We maken dan het product van al deze priemgetallen en tellen er 1 bij op.
Zo bekomen we het getal N = (2 . 3 . 5 . 7 ... p) + 1.
Nu zijn twee mogelijkheden:
- ofwel is dit een priemgetal. Maar dan hebben we meteen een contradictie met het feit dat p het grootste priemgetal zou zijn, m.a.w. we er bestaat toch een priemgetal N dat groter is dan p;
- ofwel is N zelf geen priemgetal. Maar dan heeft N een priemdeler p', die groter moet zijn dan p, want als we N delen door alle priemgetallen van 2 tot en met p is de rest telkens 1. Bijgevolg bestaat er een priemgetal p' groter dan p, wat opnieuw in contradictie is met de veronderstelling dat p het grootste priemgetal is.

In het tijdschrift American Mathematical Monthly van december 2006 publiceerde Filip Saidak, een Slovaakse wiskundige een verrassend eenvoudig nieuw bewijs van de stelling dat er oneindig veel priemgetallen zijn. Zijn bewijs luidt als volgt.
Stel n is een geheel getal groter dan 1. De getallen n en n + 1 verschillen slechts 1 en hebben dus geen gemeenschappelijke priemfactoren. Dat betekent dat het getal N₂ = n(n + 1) ten minste twee verschillende priemfactoren heeft. Voor de getallen N₂ en N₂ + 1 geldt hetzelfde: zij verschillen slechts 1 en moeten dus ten minste twee verschillende priemfactoren hebben. Het getal N₃ = N₂( N₂ + 1) = n(n + 1)[ n(n + 1) + 1] heeft dus minimaal drie verschillende priemfactoren.
Dit proces kan eindeloos worden voortgezet: het getal N_k heeft ten minste k priemfactoren. Omdat dit voor elk positief geheel getal k geldt, kan de rij priemgetallen nooit ophouden.

Filip Saidak

3 Bestaat er een algemene formule voor alle priemgetallen?
Wellicht niet, maar dit is een open probleem.
Leonard Euler merkte op dat p(n) = n² + n + 41 voor de waarden n = 0, 1, 2 ... tot en met 39 een priemgetal oplevert. Dit is niet meer waar voor n = 40 want p(40) = 40² + 40 + 41 = 1681 = 41² .

In de derde eeuw v. Chr. ontwikkelde de Griekse wiskundige Eratosthenes een algoritme waarmee hij een lijst van de priemgetallen kon opstellen. Deze methode staat bekend als de zeef van Eratosthenes.  De werkwijze wordt geïllustreerd bovenaan deze pagina. Als men de natuurlijke getallen rangschikt in rijen van 6 (zoals op de onderstaande figuur), dan blijkt dat alle priemgetallen groter dan 3 terug te vinden zijn in de eerste en de vijfde kolom. Elk priemgetal groter dan 3 is immers een zesvoud ± 1.

 

Ook de Franse monnik Marin Mersenne (1588 –  1648) zocht naar een formule voor priemgetallen. Hij onderzocht de getallen van de vorm M_p = 2^p -1, waarbij p een priemgetal is en merkte op dat  M₂ = 3, M₃ = 7, M₅ = 31 en M₇ = 127 allemaal priemgetallen zijn. Dit bleek echter niet meer waar voor M₁₁, nl. M₁₁ = 2¹¹ - 1 = 2047 = 23 . 89.


Marin Mersenne

Priemgetallen van de vorm 2^p - 1, met p een priemgetal, worden Mersenne-priemgetallen genoemd. Via de GIMPS (Great Internet Mersenne Prime Search) proberen wiskundigen via de formule van Mersenne steeds grotere priemgetallen te vinden. Deze getallen zijn immers van groot belang voor de cryptografie, de wetenschap die zich bezighoudt met het coderen van gegevens. Meer hierover lees je op http://primes.utm.edu, waar je o.a. het grootst gekende priemgetal kan vinden. Ook jij kan mee helpen zoeken naar een nieuw grootste priemgetal en misschien zo eeuwige roem of 100 000 dollar verwerven. Meer uitleg op http://www.mersenne.org/.

4 Welke open problemen rond priemgetallen houden de wiskundigen bezig?
Zoals eerder gemeld zoekt men steeds grotere priemgetallen en blijft het een open vraag of er een algemene formule bestaat voor priemgetallen.
Het meest beroemde probleem rond priemgetallen is echter de zogenaamde Goldbach-conjectuur. Christian Goldbach (1690-1764) schreef in 1742 een brief naar Euler waarin hij het vermoeden formuleerde dat elk even getal groter dan 2 de som is van twee priemgetallen. Voor zover men met computers heeft kunnen controleren blijkt dit altijd waar te zijn, maar een algemeen bewijs hiervoor is nog niet gevonden.

Kristof Scheys en Stijn Vermeeren (oudleerlingen van het Sint-Jozefscollege in Aarschot) schreven een boeiend eindwerk bijeen rond priemgetallen. Zie bijlage.

Ook op http://www.kennislink.nl/publicaties/priemgetallen kan je heel wat leren over priemgetallen.