Je leest:

Priemgetallen

Priemgetallen

Een priemgetal is een getal met precies twee delers. De rij priemgetallen begint dus zo: 2, 3, 5, 7, 11, 13, 17, … Andere voorbeelden van priemgetallen zijn 173 en 2011. Het getal 1 is niet priem: dat heeft slechts één deler, namelijk zichzelf.

De zeef van Eratosthenes

De zeef van Eratosthenes is een methode om alle priemgetallen tot een bepaalde grens te vinden. Je begint met domweg een lijst van alle getallen op te schrijven. Dan ga je alle veelvouden van 2 wegstrepen. Daarna haal je alle veelvouden van 3 weg. Zo ga je door met de veelvouden van 5, 7, 11,… Alle getallen die je overhoudt zijn priemgetallen.

Het tijdschrift Pythagoras heeft deze poster uitgegeven met daarop de zeef van Eratosthenes

Nogmaals de zeef van Erathostenes

Bewijzen van Euclides’ stelling

Al in de derde eeuw voor Christus bewees Euclides dat er oneindig veel priemgetallen zijn. Zijn bewijs (dat we tegenwoordig een bewijs uit het ongerijmde noemen) is zeer bekend, maar wat veel mensen niet weten, is dat er diverse andere bewijzen bestaan voor het feit dat er oneindig veel priemgetallen bestaan.

In 1878 kwam Ernst Eduard Kummer (1810-1893) met een kort en zeer elegant bewijs. Kummer maakt net als Euclides gebruik van een bewijs uit het ongerijmde. Andere bewijzen variëren sterk in zowel de lengte als de aanpak. Er bestaat een bewijs, eveneens uit het ongerijmde, dat gebruik maakt van getallen van de vorm 2n – 1, de zogeheten Mersenne-getallen. Hierbij wordt bewezen dat áls p het grootste priemgetal zou zijn, de priemfactoren van het getal 2p – 1 groter dan p moeten zijn, wat in tegenspraak is met de veronderstelling dat p het grootste priemgetal is.

De beroemde Leonhard Euler (1707-1783) bewees dat de reeks 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + … (in de noemers staan de priemgetallen) divergeert, dat wil zeggen: deze som kan willekeurig groot worden. Daaruit volgt dat de rij priemgetallen nooit kan ophouden, omdat dan ook de genoemde som uit slechts eindig veel termen zou bestaan.

Christian Goldbach (1690-1764) schreef in 1730 in een brief aan Euler dat hij een nieuw bewijs had gevonden voor het bestaan van oneindig veel priemgetallen. Goldbach maakt hierbij gebruik van de zogenaamde Fermat-getallen, dat zijn getallen van de vorm 22n + 1, waarbij n een niet-negatief geheel getal is.

In 1955 kwam Harry Fürstenberg met een verrassend bewijs. Hij gebruikte de topologie, een tak van de wiskunde die je niet als vanzelfsprekend in verband brengt met de getaltheorie, om de stelling van Euclides te bewijzen.

Ook nu worden nog nieuwe bewijzen gevonden. In 2006 kwam de Amerikaan Filip Saidak met een verrassend eenvoudig nieuw bewijs. In 2009 kreeg de Canadees Idris Mercer het voor elkaar om het topologische bewijs van Fürstenberg zodanig aan te passen dat van een topologisch bewijs geen sprake meer is.

Mersenne-priemgetallen

Mersenne-getallen zijn getallen van de vorm 2n – 1; het is een type getallen waarvan relatief gemakkelijk kan worden vastgesteld of ze priem zijn. De grote priemgetallen die de laatste jaren werden gevonden, zijn dan ook allemaal van deze vorm. Een getal van 40.000 cijfers past nog net op één krantenpagina; reken maar na hoeveel krantenpagina’s je nodig hebt voor 243.112.609 – 1, met 12.978.189 cijfers het grootst bekende priemgetal tot nu toe (september 2008).

Via GIMPS (Great Internet Mersenne Prime Search) kun je met je eigen computer meedoen met de jacht naar nieuwe priemgetallen. Voor de eerlijke vinders zijn er niet-geringe geldprijzen.

Priemgetallen en cryptografie

Waarom doen mensen dat nou, zoeken naar die grote priemgetallen? Nutteloos zijn dit soort getallen niet: het zijn juist deze getallen die worden gebruikt in de cryptografie om gegevens te beveiligen.

Elk willekeurig getal kan op precies één manier geschreven worden als een product van priemfactoren, bijvoorbeeld: 12 = 2 × 2 × 3, 123 = 3 × 41, 123456 = 2 × 2 × 2 x 2 × 2 × 2 x 3 × 643. Er is geen echt goed algoritme om bij een gegeven (groot) getal snel te bepalen wat deze priemfactoren zijn. Als een getal het product is van twee grote priemgetallen, dan zal het daardoor lang duren om deze twee priemfactoren te vinden. Het veel gebruikte RSA-coderingssysteem is hier op gebaseerd.

Priemgetallen en cryptografie

Onopgeloste problemen

Wiskundigen mogen dan een heleboel dingen weten over priemgetallen, er zijn ook nog heel veel onopgeloste problemen. Veel van deze problemen zijn heel eenvoudig te verwoorden, maar het is nog niemand gelukt de oplossingen te vinden – hoewel heel veel knappe koppen het al geprobeerd hebben. Op een aantal problemen zijn inmiddels fikse prijzen gezet.

Neem bijvoorbeeld het Vermoeden van Goldbach: elk even getal groter dan 2 is te schrijven als de som van twee priemgetallen. Het oogt simpel en het lijkt misschien alsof een kind de was kan doen, maar probeer maar eens een algemeen bewijs te geven!

Een ander groot open probleem is de Riemannhypothese, die er heel wat cryptischer uitziet dan het Vermoeden van Goldbach: alle niet-triviale nulpunten van de zètafunctie liggen op de kritische lijn.

Ook over priemtweelingen is nog lang niet alles bekend. Een priemtweeling is een paar van twee priemgetallen met verschil 2. Voorbeelden van priemtweelingen zijn (5, 7) en (11, 13), maar ook (1997, 1999). Af en toe wordt er een nieuwe priemtweeling gevonden (met behulp van de computer), maar of de het aantal priemgetallen eindig of oneindig is, weet nog niemand. Bijna alle experts geloven dat er inderdaad oneindig veel priemtweelingen zijn en er zijn ook plausibele vermoedens over hun verdeling, maar bewijzen ontbreken.

Kortom: er is nog veel dat we niet weten over priemgetallen. Naar aanleiding Einsteins vermeende uitspraak ‘God dobbelt niet’, zei Paul Erdös: ‘God may not play dice with the universe, but something strange is going on with the prime numbers…’

Open problemen

Priemgetallen en biologie

In de natuur zijn priemgetallen populair. Sommige cicadensoorten (‘snavelinsecten’) komen maar eens in de zeventien jaar de grond uit. Andere cicadensoorten komen elke dertien jaar de grond uit. Sommige bamboesoorten sterven juist elke zeven jaar af. Dat 17, 13 en 7 allemaal priemgetallen zijn, is geen toeval. Stel dat een cicadensoort een cyclus van twaalf jaar heeft. Deze beestjes hebben dan te vrezen van hordes natuurlijke vijanden: de dieren die elk jaar uitzwermen zijn er ook als hij uitkomt, en dieren met cycli van 2, 3, 4, 6 of 12 jaar stemmen hun cycli uiteindelijk zo af dat zij die cicaden met een cyclus van twaalf jaar zullen tegenkomen.

Een periodieke cicade

Zie ook:

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 30 juni 2008

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

LEES EN DRAAG BIJ AAN DE DISCUSSIE