Priemgetal

Een priemgetal is een natuurlijk getal groter dan 1 dat slechts twee natuurlijke getallen als deler heeft, namelijk 1 en zichzelf. Het kleinste priemgetal is dus 2, want het heeft alleen 1 en 2 als delers. Het volgende is 3, met alleen de delers 1 en 3. Het getal 4 is geen priemgetal, want het heeft behalve 1 en 4 ook 2 als deler. Een getal dat groter dan 1 is en geen priemgetal, heet een samengesteld getal. Priemgetallen vormen een belangrijk onderwerp in het deelgebied van de wiskunde dat getaltheorie genoemd wordt.

Door de afspraak dat het getal 1 geen priemgetal is, kan onder andere de hoofdstelling van de rekenkunde eenvoudiger geformuleerd worden.

De eerste 30 priemgetallen zijn 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109 en 113.

Priemgetallen werden reeds door de oude Grieken bestudeerd. Er zijn oneindig veel priemgetallen. Het bewijs hiervoor wordt gegeven door de stelling van Euclides. De oudste methode om priemgetallen te vinden is de zeef van Eratosthenes, die in de animatie hieronder wordt geïllustreerd.

Een bepaald type priemgetallen wordt gevormd door de mersennepriemgetallen. Van een mersennegetal, dat wil zeggen een getal van de vorm , kan betrekkelijk gemakkelijk vastgesteld worden of het een priemgetal is of niet.

Er is geen formule bekend die alle priemgetallen, maar geen samengestelde getallen oplevert. De verdeling van priemgetallen, dat wil zeggen, het statistische gedrag van grote aantallen priemgetallen, kan echter wel worden gemodelleerd. Het eerste resultaat in die richting was de priemgetalstelling, die, ruw gesproken, stelt dat de kans dat een gegeven, willekeurig gekozen getal  een priemgetal is, omgekeerd evenredig is met het aantal cijfers, of de logaritme van . Deze stelling is aan het einde van de 19e eeuw bewezen. De onbewezen Riemann-hypothese, die van 1859 dateert, impliceert een verfijnde verklaring hiervan met betrekking tot de verdeling van de priemgetallen.

Ondanks intensieve studie staan veel fundamentele vragen met betrekking tot priemgetallen nog steeds open. Zo zijn bijvoorbeeld het vermoeden van Goldbach, dat beweert dat elk even getal groter dan twee de som is van twee priemgetallen, en het vermoeden van de priemtweelingen, dat zegt dat er oneindig veel priemgetaltweelingen (paren van priemgetallen, waarvan het verschil gelijk is aan twee) moeten bestaan, al meer dan een eeuw onopgelost, ondanks de ogenschijnlijke eenvoud van deze uitspraken.

Priemgetallen worden toegepast in verschillende delen van de informatietechnologie, onder andere bij het beveiligen van digitale informatie, door middel van cryptografie. Met behulp van de priemgetaltest wordt bepaald dat een getal een priemgetal is. In de asymmetrische cryptografie wordt bijvoorbeeld gebruikgemaakt van de moeilijkheid om grote getallen in hun priemfactoren te ontbinden. De zoektocht naar extreem grote priemgetallen, vaak met behulp van distributed computing, heeft de studie van de priemgetallen gestimuleerd. Begin 2013 bestond het grootst bekende priemgetal uit 17 425 170 cijfers. In 2018 werd het tot nu toe grootste priemgetal ontdekt, dat volledig uitgeschreven uit 24 862 048 cijfers bestaat.

Priemgetallen en de hoofdstelling van de rekenkunde 

Het cruciale belang van priemgetallen voor de getaltheorie en de wiskunde in het algemeen komt voort uit de hoofdstelling van de rekenkunde. Priemgetallen kunnen als de "bouwstenen" van de natuurlijke getallen worden beschouwd. Zo geldt bijvoorbeeld
  ( duidt het kwadraat van 2 aan).

Zoals in dit voorbeeld te zien is, kan hetzelfde priemgetal meer keren voorkomen. De volgorde van de priemgetallen is niet belangrijk. Herschrijven van een natuurlijk getal  als het product van priemgetallen

heet het ontbinden van  in priemfactoren. Ook al zijn er verschillende algoritmen om een getal in priemfactoren te ontbinden, in het bijzonder voor grotere getallen, zij zullen allemaal dezelfde priemgetallen geven.

De verzameling van alle priemgetallen wordt wel aangeduid met .

Voorbeelden en eerste eigenschappen 

Het enige even priemgetal is 2, aangezien elk even getal, dat groter is dan twee, per definitie deelbaar door 2 is. Daarom verwijst de term oneven priemgetal naar elk priemgetal groter dan 2.

De afbeelding rechts laat op een grafische manier zien dat 12 geen priemgetal is. Priemgetallen, geschreven in het gebruikelijke decimale systeem, eindigen met uitzondering van 2 en 5, op een 1, een 3, een 7 of een 9. Dit is niet zo vreemd, omdat alle getallen die eindigen op 0, 2, 4, 6 of 8 een veelvoud van 2 en alle getallen eindigend op 0 of 5 een veelvoud van 5 zijn. Ook zijn alle priemgetallen boven de 3 van de vorm  of , omdat alle andere getallen deelbaar zijn door 2 of 3. Alle priemgetallen groter dan  zijn van de vorm , waarbij  en  geen priemfactor gemeenschappelijk heeft met  of met .  

Als  een priemgetal is en  deler is van een product  van gehele getallen, dan is  deler van , van  of van  en  allebei. Dit staat bekend als het lemma van Euclides. Het wordt gebruikt om te bewijzen, dat een getal steeds maar op één manier in priemfactoren is te ontbinden.

De Pythagoreërs ontdekten al voor 400 v.C. iets bijzonders aan bepaalde getallen. Stel een getal voor door een overeenkomstig aantal steentjes, dan kunnen de samengestelde getallen gerangschikt worden als een rechthoek. Zo kan het getal 12 gerangschikt worden als een rechthoek van 3 bij 4 steentjes. Een priemgetal kan echter niet gerangschikt worden als een echte rechthoek (anders dan een rij). Hoe het ook geprobeerd wordt, 11 steentjes kunnen niet in een rechthoek gelegd worden.

1 wel of geen priemgetal 
Wanneer 1 als priemgetal zou worden toegelaten, zou de hoofdstelling van de rekenkunde minder eenvoudig geformuleerd moeten worden, omdat dan een willekeurig aantal 1-en kon worden toegevoegd aan de manier waarop een getal in priemfactoren is te ontbinden.

Tot de 19e eeuw beschouwden de meeste wiskundigen het getal 1 als een priemgetal. De definitie luidde namelijk dat een priemgetal alleen deelbaar door 1 en zichzelf moet zijn, maar stelden geen restricties aan het aantal verschillende delers. Er is nog een grote hoeveelheid wiskundig werk dat nog steeds geldig is, ondanks het feit dat men het getal 1 toen als een priemgetal zag, zoals het werk van Stern en Zeisel. Derrick Norman Lehmers lijst van priemgetallen tot en met 10.006.721, die nog in 1956 werd herdrukt begon met 1 als het eerste priemgetal. Van Henri Lebesgue wordt gezegd dat hij de laatste professionele wiskundige was die 1 tot de priemgetallen rekende.

De priemgetallen hebben eigenschappen die voor 1 niet opgaan, zoals de relatie van het getal met zijn overeenkomstige waarde van de Euler-totiëntfunctie, of de "som-van-de-delers-functie".

Ontbinden in priemfactoren 
De hoofdstelling van de rekenkunde zegt dat elk natuurlijk getal groter dan 1 op één manier in priemfactoren is te ontbinden, dat wil zeggen kan worden geschreven als het product van priemgetallen. Er zijn verschillende algoritmen om een getal te ontbinden, zoals:
 de uitprobeermethode (soms naar het Engels "Trial-division-methode" genoemd),
 Pollards p-1-methode,
 het algoritme van Lenstra
 het algoritme van Dixon.

Uitprobeermethode 
De eenvoudigste manier om een getal  in priemfactoren te ontbinden is de uitprobeermethode, hoewel die manier niet erg efficiënt is. De methode komt erop neer de priemgetallen kleiner dan of gelijk aan , van klein naar groot te testen op deelbaarheid op . Blijkt een bepaald priemgetal  deelbaar op , dan moet  weer verder op deelbaarheid onderzocht worden, beginnend bij het priemgetal  en doorgaand tot ten hoogste .

Voorbeelden
 Bij het ontbinden 98 in priemfactoren wordt in eerste instantie gekeken naar priemgetallen kleiner of gelijk aan  (dus kleiner dan 10). 98 is deelbaar door 2: . Vervolgens wordt gekeken naar priemgetallen kleiner of gelijk aan , als deler van 49. Dan blijkt dat . Ontbonden in priemfactoren is .
 Als 143 ontbonden wordt in priemfactoren, wordt gekeken naar priemgetallen kleiner of gelijk aan , dus priemgetallen tot en met 11. Het blijkt dat 143 niet deelbaar is door 2, 3, 5 of 7, maar wel door 11, want . Het getal 13 is eveneens een priemgetal, dus ontbonden in priemfactoren is .

Het aantal priemgetallen 

Er zijn oneindig veel priemgetallen. Het oudst bekende bewijs voor deze uitspraak, waaraan soms wordt gerefereerd als de stelling van Euclides, wordt toegeschreven aan de oud-Griekse wiskundige Euclides. Euclides drukte zijn resultaat als volgt uit: "er zijn meer dan enig gegeven [eindig] aantal priemgetallen". Zijn bewijs ziet er in essentie als volgt uit:

Beschouw een eindige verzameling van priemgetallen, bijvoorbeeld 3, 5, 37. Vermenigvuldig al deze priemgetallen met elkaar en tel 1 bij dit resultaat op. Het resulterende getal, 3×5×37+1=556, is nu niet deelbaar door een van de priemgetallen uit de eindige verzameling waarmee begonnen is, aangezien dit altijd een rest van 1 geeft. Omdat alle niet-priemgetallen te schrijven zijn als een product van priemgetallen, is ofwel dit resulterende getal zelf een priemgetal ofwel moet er een priemgetal zijn, waardoor het resulterende getal deelbaar is, maar dat niet zit in de oorspronkelijke eindige verzameling van priemgetallen waarmee begonnen is. Hoe dan ook, er is dus nog ten minste één priemgetal dat geen deel uitmaakte van de eindige verzameling, waarmee begonnen werd. Dit argument is van toepassing ongeacht de eindige verzameling waarmee de redenering begonnen wordt. Er bestaan dus altijd meer priemgetallen dan enig gegeven eindig getal. (Euclides, Elementen: Boek IX, Propositie 20)

De argumentie van Euclides verklaart dat als  het product is van een eindig aantal priemgetallen, het getal  deelbaar moet zijn door een priemgetal (eventueel zichzelf), dat geen deel uitmaakt van het oorspronkelijke aantal.

Het bewijs wordt soms op een manier geformuleerd die lezers op het verkeerde been kan zetten en ten onrechte doet geloven dat  zelf priem moet zijn. Zij denken dat het bewijs van Euclides zegt dat het priemproduct plus 1 zelf altijd een priemgetal is. Deze verwarring ontstaat, wanneer het bewijs wordt gepresenteerd als een bewijs uit het ongerijmde waarbij verondersteld wordt dat er maar eindig veel priemgetallen zijn. Het getal  is daarbij het product van al deze priemgetallen en er wordt geconcludeerd dat, omdat  niet deelbaar is door enig priemgetal, het zelf een priemgetal is, wat een tegenspraak inhoudt (citaat G.H. Hardy). Dit voert lezers soms tot de onterechte conclusie, dat als  het product van de eerste  priemgetallen is, het getal  ook een priemgetal is. Deze conclusie leunt op een hypothese die later onwaar blijkt te zijn, en kan daarom niet als bewezen worden beschouwd. Het kleinste tegenvoorbeeld met een samengesteld getal  is:

De getallen 59 en 509 zijn beide priemgetallen die niet in de oorspronkelijke reeks voorkomen.

Er zijn veel meer bewijzen voor de oneindigheid van het aantal priemgetallen bekend. Een daarvan is dat de som van de reciproquen van alle priemgetallen resulteert in een divergerende reeks, en er dus meer dan eindig veel priemgetallen moeten zijn

Het bewijs hiervan is afkomstig van Euler. Meer in het bijzonder: als  de som aanduidt van de reciproquen van alle priemgetallen  met , dan geldt dat
 voor  ( staat voor de grote-O-notatie).

Een ander bewijs, gebaseerd op eigenschappen van Fermat-priemgetallen werd door Goldbach gegeven.
Kummers bewijs is bijzonder elegant en Harry Furstenberg geeft zijn bewijs van Furstenberg over de oneindigheid van het aantal priemgetallen met hulp van de algemene topologie.

Niet alleen zijn er oneindig veel priemgetallen, de stelling van Dirichlet over rekenkundige rijen stelt dat in elke rekenkundige rij  waarin de positieve gehele getallen  en  relatief priem zijn, oneindig veel priemgetallen voorkomen. De recente stelling van Green-Tao laat zien dat er van elke lengte rekenkundige rijen zijn die uit priemgetallen bestaan.

Verificatie van priemgetallen 

Om priemgetallen te gebruiken, is verificatie dat een gegeven getal n al of niet een priemgetal is van cruciaal belang. Er zijn verschillende manieren om dit doel te bereiken. Een zeef is een algoritme dat alle priemgetallen tot en inclusief een bepaalde limiet oplevert. De oudste dergelijke zeef is de zeef van Eratosthenes (zie hierboven). De zeef van Erasthones is handig voor relatief kleine priemgetallen. De moderne zeef van Atkin is ingewikkelder, maar, wanneer hij goed wordt geoptimaliseerd, ook sneller. Vóór de komst van computers werd er vaak gewerkt met lijsten van priemgetallen tot een grens van 107.

In de praktijk wil men vaak direct controleren of een gegeven getal al of niet een priemgetal is, in plaats van eerst een lijst van priemgetallen te genereren, zoals in de twee hierboven genoemde zeefalgoritmes. De eenvoudigste methode om dit te doen, beter bekend als proefdeling, werkt als volgt: gegeven een getal , deel  door alle getallen , kleiner dan of gelijk aan de wortel van het getal, . Als een van de delingen een geheel getal oplevert, dan is het oorspronkelijke getal geen priemgetal, anders is het wel een priemgetal. In de praktijk volstaat het om deze proefdeling voor  priemgetallen te doen. Hoewel het een eenvoudig algoritme is, wordt het snel onpraktisch om te testen of een groot getal een priemgetal is aangezien het aantal mogelijke factoren te snel groeit als het te testen getal in grootte toeneemt. Volgens de priemgetalstelling die hieronder uiteen wordt gezet ligt het aantal priemgetallen kleiner dan  in de buurt van . Om  te controleren met de priemgetaltest is de grootste priemfactor die nodig is iets minder dan  en het aantal van zulke priemfactorkandidaten zou dicht in de buurt liggen van . Dit aantal neemt steeds langzamer toe naarmate  groter wordt, maar omdat er belangstelling is voor grote waarden van , is de telling ook groot: voor  bedraagt zij 450 miljoen.

Moderne priemgetaltestalgoritmen kunnen worden onderverdeeld in twee hoofdklassen, deterministische- en probabilistische (of "Monte Carlo"-) algoritmen. Met probabilistische algoritmen kan men vaststellen of een samengesteld getal een priemgetal is, maar zijn zeker niet in staat om priemgetallen te identificeren als samengestelde getallen; deterministische algoritmen hebben aan de andere kant niet de mogelijkheid van dergelijke vergissingen. Het belang van probabilistische algoritmen ligt in het feit dat ze vaak sneller dan deterministische algoritmen zijn; bovendien is voor de meeste van dergelijke algoritmen de kans dat men een samengesteld getal ten onrechte als een priemgetal identificeert bekend. Deze algoritmen kiezen typisch een willekeurig getal , dat de "getuige" wordt genoemd, en checken vervolgens een formule, waarbij zowel de getuige als het potentiële priemgetal  voorkomen. Na een aantal iteraties, verklaren zij dat of  "zeker samengesteld" of "waarschijnlijk priem" is. De Fermatpriemgetaltest beroept zich bijvoorbeeld op de kleine stelling van Fermat (zie hierboven). Als dus
,

dan is  zeker samengesteld.  kan echter ook samengesteld zijn, als  voor alle getuigen , namelijk als  een Carmichael-getal is. In het algemeen zullen samengestelde getallen die, ongeacht de gekozen getuige, voor de desbetreffende test "waarschijnlijk priem" worden verklaard, pseudopriemgetallen worden genoemd. De populairste probabilistische tests hebben echter geen last van dit nadeel. De onderstaande tabel vergelijkt een aantal priemgetaltesten. De lopende tijd wordt gegeven in termen van , het getal waarop getest wordt, en voor probabilistische algoritmen, het aantal  van de uitgevoerde testen.

{| class="wikitable"
! Test
! Ontwikkeld in
! Deterministisch
! Lopende tijd
! Notities
|-
| AKS-test
| 2002
| Ja
| 
|
|-
| Priemtest van Fermat
|
| Nee
| 
| faalt voor Carmichael-getallen
|-
| Lucas-priemgetaltest
|
| Ja
|
| vereist factorisatie van 
|-
| Solovay-Strassen-priemgetaltest
| 1977
| Nee, foutwaarschijnlijkheid 
| 
|
|-
| Miller-Rabin-priemgetaltest
| 1980
| Nee, foutwaarschijnlijkheid 
| 
|
|-
| Elliptische kromme-priemgetaltest
| 1977
| Nee
| 
| heuristische lopende tijd
|}

Speciale typen van priemgetallen 

Er zijn vele bijzondere typen priemgetallen; er zijn er die bijvoorbeeld gekwalificeerd worden door verschillende formules, of door de decimale cijfers in beschouwing te nemen. Priemgetallen van de vorm , waarin  een priemgetal is, staan bekend als mersennepriemgetallen. Hun belang ligt in het feit dat er relatief snelle priemgetaltestalgoritmen voor het testen van mersennepriemgetallen bestaan.

Priemgetallen van de vorm  staan bekend als Fermat-priemgetallen; een regelmatige -hoek is dan en slechts dan construeerbaar met passer en liniaal als
,
waarin  een product van enig aantal verschillende Fermat-priemgetallen en  een willekeurig natuurlijk getal is, inclusief nul. Er zijn slechts vijf Fermat-priemgetallen bekend: 3, 5, 17, 257 en 65.537.

Priemgetallen , waarbij  ook een priemgetal is, staan bekend als de Sophie Germainpriemgetallen. Een priemgetal  noemt men primoriaal of priem-factoriaal, indien voor enig getal  dit priemgetal de vorm heeft
, 
waarin  staat voor het product  van alle priemgetallen . Een priemgetal wordt factoriaal genoemd als het van de vorm  is. Het is niet bekend of er oneindig veel primoriale of factoriale priemgetallen zijn.

Het grootste bekende priemgetal 
Sinds de uitvinding van de elektronische computers is het grootst bekende priemgetal bijna altijd een mersennepriemgetal geweest, dit omdat er een bijzonder snelle priemgetaltest, de Lucas-Lehmertest voor mersennegetallen, voor het vinden van getallen van deze vorm bestaat. Het grootste bekende priemgetal (gevonden in december 2018) is het getal 282 589 933-1 en bestaat uit 24 862 048 cijfers. De volgende tabel geeft de grootste bekende priemgetallen van de genoemde soorten:

{| class="wikitable" border="1"
! Priemgetal
! Aantal decimale cijfers
! Soort
! Datum
! Gevonden door
|-
| 282 589 933 − 1
| 24 862 048
| mersennepriemgetal
| december 2018
| Patrick Laroche (Gimps)
|-
| 277 232 917 − 1
| 23 249 425
| mersennepriemgetal
| 26 december 2017
| Jon Pace
|-
| 19 249 × 213 018 586 + 1
| 3 918 990
| niet een mersennepriemgetal (Proth-getal)
| 26 maart 2007
| Seventeen or Bust
|-
| 150 209! + 1
| 712 355
| factoriaal priemgetal
| oktober 2012
| PrimeGrid
|-
| 1 098 133# - 1
| 476 311
| primoriaal priemgetal
| maart 2012
| PrimeGrid
|-
| 3 756 801 695 685 × 2666 669 ± 1
| 200 700
| priemtweeling
| december 2011
| PrimeGrid
|}

Sommige van de grootste priemgetallen, waarvan niet bekend is of zij een bepaalde vorm hebben (dat wil zeggen dat zij niet door een eenvoudige formule, zoals die voor de mersennepriemgetallen gegenereerd zijn) zijn gevonden door een stuk semi-willekeurige binaire data te nemen, deze naar een getal te converteren, dit voor sommige positieve gehele getallen  met  te vermenigvuldigen en vervolgens te zoeken naar mogelijke priemgetallen binnen het interval .

De Electronic Frontier Foundation heeft in 2009 een prijs van 100.000 dollar toegekend aan Great Internet Mersenne Prime Search (GIMPS) voor het als eerste ontdekken van een priemgetal dat ten minste uit 10 miljoen cijfers bestaat. Door dezelfde organisatie zijn ook prijzen van respectievelijk 150.000 en 250.000 dollar uitgeloofd voor priemgetallen van respectievelijk minimaal 100 miljoen en 1 miljard cijfers.

Genereren van priemgetallen 
Er bestaat geen bekende formule om priemgetallen te genereren die efficiënter is in het vinden van priemgetallen dan de hierboven genoemde methoden.

Er bestaat een verzameling van diofantische vergelijkingen in 9 variabelen en een parameter met de volgende eigenschap: de parameter is dan en slechts dan een priemgetal als het daaruit voortvloeiende stelsel van vergelijkingen een oplossing heeft over de natuurlijke getallen. Deze oplossing kan worden gebruikt om een enkele formule te verkrijgen met de eigenschap dat al haar positieve waarden priemgetallen zijn.

Een andere formule is gebaseerd op de hierboven genoemde stelling van Wilson en genereert vele keren het getal 2 en alle andere priemgetallen precies één keer. Er bestaan soortgelijke formules die ook priemgetallen produceren.

Geschiedenis 
Er bevinden zich in de overgeleverde nalatenschap van het Oude Egypte hints, dat men enige kennis over de priemgetallen bezat: de Egyptische fractie uitbreidingen in de Rhind-papyrus, hebben bijvoorbeeld verschillende vormen voor priemgetallen en voor samengestelde getallen. De oudste overgeleverde documenten aangaande de expliciete studie van priemgetallen komen echter van de Oude Grieken. De uit circa 300 v.Chr. stammende Elementen van Euclides bevat belangrijke stellingen over priemgetallen, met inbegrip van het bewijs van de oneindigheid van het aantal priemgetallen en de hoofdstelling van de rekenkunde. Euclides liet ook zien hoe men een perfect getal uit een mersennepriemgetal kon construeren. De Zeef van Eratosthenes, die wordt toegeschreven aan Eratosthenes, is een eenvoudige methode om priemgetallen te berekenen, hoewel de grote priemgetallen, die vandaag de dag met behulp van computers worden gevonden, op een andere manier worden gegenereerd.

Na de oude Grieken gebeurde er tot de 17e eeuw niet veel met betrekking tot de studie van priemgetallen. In 1640 stelde Pierre de Fermat (overigens zonder bewijs) zijn kleine stelling van Fermat (die later werd bewezen door Leibniz en Euler). Een speciaal geval van de stelling van Fermat was mogelijk al eerder bekend aan Chinese wiskundigen. Fermat vermoedde dat alle getallen van de vorm  priem zijn (ze worden naar hem fermatgetallen genoemd) en hij verifieerde dit tot en met  (of ). Het volgende fermatgetal, , bleek echter een samengesteld getal te zijn (een van de priemfactoren is 641), zoals Euler later ontdekte, en waarschijnlijk zijn er evenmin grotere fermatgetallen die priem zijn. De Franse monnik Marin Mersenne bestudeerde priemgetallen van de vorm , waarin  een priemgetal is. Dit type priemgetallen wordt naar hem mersennepriemgetalen genoemd.

Bij Eulers werk in de getaltheorie zaten vele resultaten met betrekking tot priemgetallen. Hij toonde aan dat de oneindige reeks  divergeert.
In 1747 toonde hij aan dat de even perfecte getallen exact de gehele getallen van de vorm  zijn, waar de tweede priemfactor een mersennepriemgetal is.

Aan het begin van de 19e eeuw, uitten Legendre en Gauss onafhankelijk van elkaar het vermoeden, dat als  naar oneindig nadert, het aantal priemgetallen tot en met  asymptotisch naar  nadert, waarin  de natuurlijke logaritme van  is. Ideeën van Riemann in zijn artikel uit 1859 over de zèta-functie schetsten de contouren van een programma, dat bijna veertig jaar later zou leiden tot een bewijs van de priemgetalstelling. Deze contouren werden in 1896 door zowel Hadamard als de la Vallée Poussin ingekleurd en afgewerkt. Beide wiskundigen vonden in hetzelfde jaar onafhankelijk van elkaar een bewijs voor de priemgetalstelling.

Voor het bewijzen dat een getal een priemgetal is, wordt (voor grote aantallen) geen gebruik van proefdelingen gemaakt. Veel wiskundigen hebben aan priemgetaltesten voor grote getallen gewerkt, waarbij zij zich vaak tot specifieke getalvormen hebben beperkt.
Hiertoe behoren onder andere de Pépin-testen voor fermatgetallen (1877), de stelling van Proth (rond 1878) en de Lucas-Lehmer-priemgetaltest (dateert oorspronkelijk uit 1856), en de veralgemeende Lucas-priemgetaltest. Meer recente algoritmen zoals de APRT-CL, het ECPP en de AKS-test werken op willekeurige getallen, maar blijken veel langzamer dan meer specifieke priemgetaltesten.

Gedurende lange tijd dacht men dat priemgetallen slechts een zeer beperkte toepassing buiten zuivere wiskunde zouden kunnen vinden; dit veranderde echter in de jaren 1970, toen de concepten van de asymmetrische cryptografie werden uitgevonden. Hierin vormden priemgetallen de basis voor de eerste algoritmen, zoals het RSA-cryptografie-algoritme.

Sinds 1951 zijn alle grootst bekende priemgetallen gevonden met behulp van computers. Het zoeken naar steeds grotere priemgetallen heeft ook grote interesse gegenereerd buiten wiskundige kringen. De Great Internet Mersenne Prime Search en andere distributed computing-projecten om grote priemgetallen te vinden zijn in de afgelopen tien tot vijftien jaar populair geworden, terwijl de wiskundigen zelf blijven worstelen met de getaltheorie achter de priemgetallen.

Verdeling van de priemgetallen 

Gezien het feit dat er een oneindig aantal priemgetallen bestaat, is het vanzelfsprekend om naar patronen of onregelmatigheden in de verdeling van priemgetallen te zoeken. Het probleem van het modelleren van de verdeling van de priemgetallen is voor het aantal getaltheoretici een populair onderzoeksonderwerp. Het optreden van individuele priemgetallen tussen de natuurlijke getallen is (tot dusver) onvoorspelbaar, ook al zijn er wetten (zoals de priemgetalstelling en het postulaat van Bertrand), die hun gemiddelde verdeling regeren. Leonhard Euler sprak hierover meer dan 200 jaar geleden de volgende woorden:
 Wiskundigen hebben tot nu toe tevergeefs geprobeerd om enige volgorde te ontdekken in de reeks priemgetallen, en men is geneigd te denken dat dit een mysterie is dat de menselijke geest nooit zal doorgronden.

In 1975 merkte Don Zagier tijdens een lezing het volgende op
 Er zijn twee feiten over de verdeling van priemgetallen, waarvan ik U zo overweldigend hoop te overtuigen dat zij permanent in uw geheugen gegrift staan. Het eerste is dat, ondanks hun eenvoudige definitie en rol als bouwstenen van de natuurlijke getallen, de priemgetallen tussen de natuurlijke getallen als onkruid groeien, waarbij zij schijnbaar aan geen andere wet dan aan de wetten van het toeval gehoorzamen, en niemand kan voorspellen, waar het volgende priemgetal zal opduiken. Het tweede feit is des te meer verbazingwekkend, want het stelt precies het tegenovergestelde: de priemgetallen vertonen een verbluffende regelmaat, er bestaan wetten die hun gedrag regeren, en de priemgetallen gehoorzamen met bijna militaire precisie aan deze wetten. 

Euler merkte op dat de functie  priemgetallen geeft voor  (maar niet noodzakelijkerwijs voor een grotere ), een opmerkelijk feit, dat bij nadere beschouwing tot diepe algebraïsche getaltheorie, meer specifiek de Heegner-getallen, leidt. De spiraal van Ulam toont alle natuurlijke getallen op een spiraalachtige manier. Verrassend genoeg clusteren priemgetallen op bepaalde diagonalen, maar niet op andere.

Het aantal priemgetallen onder een gegeven aantal 

De priemgetal-telfunctie  wordt gedefinieerd als het aantal priemgetallen tot en met . Bijvoorbeeld: , aangezien er vijf priemgetallen kleiner dan of gelijk aan 11 zijn. Er zijn bekende algoritmen om exacte waarden van  sneller te berekenen dan het mogelijk is om het priem zijn van elk getal tot en met  te berekenen. Waarden zo groot als  kunnen met moderne computers snel en nauwkeurig worden berekend.

Voor grotere waarden van , buiten het bereik van moderne computerapparatuur, geeft de priemgetalstelling een schatting:  is bij benadering gelijk aan . Met andere woorden, als  zeer groot wordt, is de waarschijnlijkheid dat een getal kleiner dan  een priemgetal is, omgekeerd evenredig aan het aantal cijfers van dit getal . Er zijn nog betere schattingen bekend; zie bijvoorbeeld Priemgetalstelling#De priemgetal-telfunctie in termen van de logaritmische integraalfunctie.

Als  een positief geheel getal groter dan 1 is, bestaat er altijd een priemgetal , zodanig dat  (postulaat van Bertrand).

Hiaten tussen priemgetallen 

Een reeks van opeenvolgende gehele getallen, die geen van allen een priemgetal zijn, noemt men priemgetalhiaat. Er bestaan priemgetalhiaten van willekeurige lengte: voor elk natuurlijk getal  groter dan 1 is de rij (voor een uitleg over de notatie  lees het artikel faculteit)

een rij van  opeenvolgende samengestelde gehele getallen, omdat

samengesteld is voor elke .

Aan de andere kant kunnen priemgetalhiaten ook willekeurig klein worden in verhouding tot de priemgetallen: het quotiënt
,

waarin  het -de priemgetal aanduidt (dat wil zeggen dat  enz.), benadert nul als  naar oneindig nadert.

Open vragen

De Riemann-hypothese 

De riemann-hypothese is een van de oudste vermoedens waarvoor nog geen wiskundig bewijs is gevonden. Bernhard Riemann schreef het in 1859 op. Om de riemann-hypothese te kunnen formuleren is het noodzakelijk eerst de riemann-zèta-functie te begrijpen, die voor een complex getal  met het reële deel groter dan 1 gedefinieerd is als:

De tweede gelijkheid is een gevolg van de hoofdstelling van de rekenkunde en laat zien dat er een nauw verband tussen zèta-functie en de verdeling van de priemgetallen is. Het hierboven genoemde feit bijvoorbeeld, dat er oneindig veel priemgetallen bestaan, kan worden afgelezen uit de divergentie van de harmonische rijen:

Een ander voorbeeld van de rijkdom van de zèta-functie en een glimp van de moderne algebraïsche getaltheorie is de volgende identiteit, het Bazel-probleem, opgesteld door Euler,

De riemann-hypothese gaat over de nulpunten van de zèta-functie. De verbinding met priemgetallen is dat de riemann-hypothese in essentie zegt dat de priemgetallen zo regelmatig verdeeld zijn als mogelijk is. Het vermoeden stelt natuurkundig ruwweg, dat de onregelmatigheid in de verdeling van priemgetallen alleen afkomstig is van willekeurige ruis. De priemgetalstelling  zegt dat ongeveer  van alle getallen kleiner dan  priemgetallen zijn, maar de riemann-hypothese stelt dat de asymptotische verdeling van priemgetallen ook geldig is voor veel kortere intervallen over de vierkantswortel van , voor de intervallen in de buurt van . De riemann-hypothese wordt algemeen verondersteld waar te zijn.

Andere vermoedens 
Naast de riemann-hypothese zijn er veel meer vermoedens over priemgetallen, waarvan velen al heel oud zijn: bijvoorbeeld alle vier de problemen van Landau uit 1912 (het vermoeden van Goldbach, priemtweelingen, vermoeden van Legendre en het vermoeden over  priemgetallen) zijn tot op heden nog steeds onopgelost.

Veel vermoedens gaan over de vraag of, als er sprake is van bepaalde additionele eigenschappen, er oneindig veel priemgetallen bestaan die deze eigenschappen hebben. Het wordt vermoed dat er bijvoorbeeld oneindig veel fibonacci-priemgetallen en oneindig veel mersennepriemgetallen bestaan, maar men vermoedt dat het aantal fermat-priemgetallen niet oneindig is. Het is niet bekend of er oneindig veel priem-euclides-getallen bestaan.

Een aantal vermoedens heeft betrekking op aspecten van de verdeling van priemgetallen. Men vermoedt dat er oneindig veel priemtweelingen, paren van priemgetallen met verschil 2, (priemtweelingvermoeden) bestaan. Het vermoeden van Polignac is een aanscherping van dat vermoeden, in die zin dat dit vermoeden uitspreekt dat voor elk positief geheel getal , er oneindig veel paren van opeenvolgende priemgetallen bestaan, die van elkaar met  afwijken. Het vermoeden van Brocard zegt dat er altijd ten minste vier priemgetallen tussen de kwadraten van opeenvolgende priemgetallen groter dan 2 zitten. Het vermoeden van Legendre stelt dat er een priemgetal tussen  en  bestaat voor elk positief geheel getal . Dit laatste vermoeden wordt geïmpliceerd door het sterkere vermoeden van Cramér.

Andere vermoedens hebben betrekking op additieve aspecten van getallen en priemgetallen: het vermoeden van Goldbach stelt dat elk even getal groter dan 2 geschreven kan worden als een som van twee priemgetallen, terwijl de zwakke versie vermoedt dat elk oneven geheel getal groter dan 5 geschreven kan worden als een som van drie priemgetallen.

Toepassingen 
Voor een lange tijd werd de getaltheorie, en in het bijzonder de studie van priemgetallen, gezien als het kanonieke voorbeeld van de zuivere wiskunde, met geen enkele toepassingen buiten het belang van het bestuderen van het onderwerp zelf. In het bijzonder waren getaltheoretici, zoals de Britse wiskundige G. H. Hardy er trots op werk te doen, dat absoluut geen enkele militaire betekenis had Deze visie werd echter in de jaren 1970 verbrijzeld toen in het openbaar werd aangekondigd dat priemgetallen konden worden gebruikt als basis voor de creatie van asymmetrische cryptografie-algoritmen. Priemgetallen worden nu ook gebruikt voor hashtabellen en pseudowillekeurigegetallengeneratoren.

Sommige rotormachines werden met een verschillend aantal pinnen op elke rotor ontworpen, waarbij het aantal pinnen op elke rotor ofwel priem ofwel relatief priem ten opzichte van het aantal pinnen op elke andere rotor was. Deze ontwerpbeslissing hielp de volledige cyclus van mogelijke rotorposities te genereren voordat enige positie herhaald wordt.

Modulair rekenen met priemgetal 

Modulair rekenen is een variant van de gebruikelijke rekenkunde. Bij het "rekenen modulo" een vast getal  vinden de berekeningen plaats in de eindige verzameling  en worden resultaten steeds gereduceerd met zoveel veelvouden van  dat het eindresultaat in deze verzameling ligt. 

In het algemeen is echter niet mogelijk om in deze setting te delen. Voor bijvoorbeeld  heeft de vergelijking

geen oplossing , die het analogon zou zijn van 2/3. Het onderscheidend kenmerk is dat in de modulaire rekenkunde dan en slechts dan deling modulo  mogelijk is als  een priemgetal is. Zo heeft de vergelijking

de unieke oplossing . Op equivalent wijze is  dan en slechts dan een priemgetal, als alle gehele getallen  relatief priem zijn ten opzichte van , dat wil zeggen dat hun grootste gemene deler gelijk is aan 1. 

De verzameling  met optellen en vermenigvuldigen wordt aangeduid als . Sommige stellingen kunnen op een abstracte manier worden afgeleid uit de beschouwing van . De kleine stelling van Fermat bijvoorbeeld, waarin wordt gesteld dat  voor elk geheel getal  deelbaar is door , kan met behulp van deze worden bewezen. Een gevolg hiervan is het volgende: als  een priemgetal anders dan 2 en 5 is, dan is  een repeterende breuk, waarvan de periode gelijk is aan  of een deler van . De breuk , uitgedrukt met het grondtal  (in plaats van 10), heeft dezelfde eigenschap, op voorwaarde dat  geen priemfactor van  is. De stelling van Wilson zegt dat een geheel getal  dan en slechts dan een priemgetal is, als de faculteit  deelbaar is door . Bovendien is een geheel getal  dan en slechts dan een samengesteld getal, als  deelbaar is door .

Groepentheorie 
Veel wiskundige deelgebieden maken intensief gebruik van priemgetallen. Een voorbeeld uit de theorie van de eindige groepen zijn de stellingen van Sylow: als  een eindige groep is en  de hoogste macht van het priemgetal  is, die de orde van  deelt, dan heeft  een deelgroep van orde . Elke groep met een priemorde is dus cyclisch (stelling van Lagrange).
Als  een eindige groep is en  een priemgetal is, dat de orde van  deelt, dan bevat  een element van orde  (stelling van Cauchy).

Publiekesleutelcryptografie 

Verschillende publiekesleutelcryptografie-algoritmen, zoals RSA of het Diffie-Hellman-sleuteluitwisselingsprotocol zijn gebaseerd op zeer grote priemgetallen (die bijvoorbeeld uit 512 bits bestaan). Deze algoritmen vertrouwen op het feit dat het veel gemakkelijker is om twee heel grote getallen,  en  met elkaar te vermenigvuldigen, met als resultaat , dan om het omgekeerde te doen, en uit  de waarde van  en  terug te rekenen, indien deze  en  relatief priem zijn.

Priemgetallen in de natuur 
Onvermijdelijk zijn enkele van de getallen die in de natuur voorkomen priemgetallen. Er zijn echter relatief weinig voorbeelden van getallen die in de natuur voorkomen juist omdat zij priemgetallen zijn.

Een voorbeeld van het gebruik van priemgetallen in de natuur is als een evolutionaire strategie die door cicaden van het geslacht Magicicada lijkt te worden gebruikt. Deze insecten brengen het grootste deel van hun leven als larven ondergronds door. Ze verpoppen zich en komen vervolgens pas na 13 of 17 jaar uit hun holen, waarna zij rondvliegen, paren en dan na hoogstens een paar weken sterven. De logica van de 13- en 17-jarige cyclus is dat men veronderstelt dat deze priemgetalintervallen het voor roofdieren erg moeilijk maken zich in een richting te ontwikkelen dat zij zich in enige mate als roofdieren op Magicicadas kunnen specialiseren Als Magicicadas met niet-priemgetal-tussenpozen zou verschijnen, zeg elke 12 jaar, dan zouden roofdieren, die elke 2, 3, 4, 6 of 12 jaar zouden verschijnen er zeker van kunnen zijn om Magicicades exemplaren tegen te komen om deze vervolgens te verorberen. Door natuurlijke selectie zouden zij hier langzamerhand beter in kunnen worden. Over een 200-jarige periode zou de gemiddelde roofdierbevolking tijdens hypothetische uitbraken van 14- en 15-jaar cicaden tot 2% hoger zijn dan tijdens uitbraken van 13- en 17-jaar cicaden. Hoewel klein lijkt dit voordeel genoeg te zijn om de natuurlijke selectie in de richting van een priem-genummerde levenscyclus van deze insecten te sturen.

Er wordt gespeculeerd dat de nulpunten van de zèta-functie verbonden zijn met de energieniveaus van complexe kwantumsystemen.

Priemgetallen in de techniek 
Bij de aandrijving met behulp van kamwielen, zoals toegepast in windmolens, zou het aantal kammen in een kamwiel een priemgetal moeten zijn. Hierdoor raken dezelfde kammen van de twee wielen elkaar pas weer na het aantal omwentelingen van de as dat het product van de twee aantallen kammen is. Hierdoor treedt een lagere en gelijkmatigere slijtage op.

Enkele eigenschappen van priemgetallen 
 Als  een priemgetal is en  deelt een product  van natuurlijke getallen, dan is  een deler van  of van  (zie ook hierboven). Deze eigenschap werd bewezen door Euclides en is bekend als Het lemma van Euclides. Het is gebruikt in sommige bewijzen van de uniciteit van de ontbinding in priemfactoren.
 De ring  (zie modulair rekenen) is een lichaam (in België: veld) ofwel eindig lichaam dan en slechts dan als  een priemgetal is. Anders gezegd:  is een priemgetal dan en slechts dan als de totiëntfunctie .
 Als  een priemgetal is en  is een willekeurig geheel getal, dan is  deelbaar door  (kleine stelling van Fermat).
 Als  een priemgetal is anders dan 2 en 5, dan is  altijd een repeterende breuk, met een periode van  of een deler van . Deze kan direct van de kleine stelling van Fermat afgeleid worden.  uitgedrukt in een ander grondtal  (dus anders dan grondtal 10) heeft het vergelijkbare effect, gegeven dat  geen priemfactor is van  (zie repeterende breuk voor enkele interessante eigenschappen).
 Een geheel getal  is een priemgetal dan en slechts dan als  deelbaar is door  (stelling van Wilson); hierbij staat het uitroepteken voor de faculteit. Omgekeerd, een geheel getal  is samengesteld dan en slechts dan als  deelbaar is door .
 Als  een positief geheel getal is, dan is er altijd een priemgetal  met   (Postulaat van Bertrand).
 Sommering van de omgekeerden van alle priemgetallen resulteert in een divergente reeks. Meer precies, als  de som van de omgekeerden van alle priemgetallen  is met , dan  voor  (zie Grote-O-notatie).
 Alle priemgetallen hebben de vorm  of , met als enige uitzonderingen 2 en 3, omdat de andere mogelijkheden alle deelbaar zijn door 2 of 3.
 Voor ieder priemgetal , bestaat er een natuurlijk getal  zodat .
 Voor ieder priemgetal , bestaat er een natuurlijk getal  zodat .
 Voor ieder priemgetal , bestaat er een natuurlijk getal  zodat .
 De karakteristiek van ieder lichaam (in België: veld) is nul of een priemgetal.
 Als  een eindige groep is en  is de hoogste macht van het priemgetal  dat de orde van  deelt, dan heeft  een subgroep van orde  (Stellingen van Sylow).
 Als  een priemgetal is en  is een groep met  elementen, dan bevat  een element van de orde .
 De priemgetalstelling zegt dat het aantal priemgetallen kleiner dan  asymptotisch  nadert.

Onbeantwoorde vragen over priemgetallen 
Er zijn veel onbeantwoorde vragen op het gebied van priemgetallen:
 Het vermoeden van Goldbach: Kan ieder even getal geschreven worden als de som van twee priemgetallen?
 Priemtweelingvermoeden: Een priemtweeling is een paar priemgetallen dat twee verschilt, zoals 11 en 13. Zijn er oneindig veel priemtweelingen?
 Bevat de rij van Fibonacci oneindig veel priemgetallen?
 Zijn er oneindig veel fermat-priemgetallen?
 Is er een priemgetal tussen  en  voor elke ?
 Zijn er oneindig veel priemgetallen van de vorm ?
 Is het mogelijk een getal efficiënt (dat wil zeggen in polynomiale tijd) in priemfactoren te ontbinden?
 Waarom komen priemgetallen vaker voor op bepaalde diagonalen in de spiraal van Ulam dan op andere?

Generalisaties 
Het concept van priemgetal is zo belangrijk dat het in verschillende deelgebieden van de wiskunde een algemene vorm heeft gekregen. In het algemeen geeft "priem" op toepasselijke wijze aan dat een wiskundig object niet verder ontleedbaar is. Het priemlichaam bijvoorbeeld is het kleinste deellichaam van een lichaam (in België: veld) . Het is ofwel  of het eindige lichaam met  elementen, vandaar de naam. Vaak wordt er een tweede, extra betekenis bedoeld met het woord priem, namelijk dat elk object, op een in essentie unieke wijze, kan worden uitgesplitst in haar priemcomponenten. In de knopentheorie bijvoorbeeld is een priemknoop een knoop die niet kan worden geschreven als de verbonden som van twee triviale knopen. Elke knoop kan uniek worden uitgedrukt als een verbonden som van priemknopen.  Priemmodellen en priem 3-variëteiten zijn andere voorbeelden van dit type.

Ringtheorie 
In de ringtheorie beschouwt men als priemelement van een ring het element  dat de eigenschap heeft dat voor willekeurige elementen  en  geldt dat wanneer  deelbaar is door , er moet gelden dat  of  deelbaar is door  (of allebei). Uit deze definitie volgt dat een additieve inverse van een priemelement eveneens een priemelement is. Het is echter bewijsbaar dat in gangbare getallenverzamelingen, zoals de gehele getallen, een getal een priemgetal is dan en slechts dan als het irreducibel is.

Priemidealen 

In de ringtheorie wordt de notie van getal in het algemeen vervangen door die van een ideaal. Priemidealen, die priemelementen in die zin veralgemenen dat de hoofdideaal, die door een priemelement wordt gegenereerd een priemideaal is, zijn een belangrijk instrument en object van studie in de commutatieve algebra, de algebraïsche getaltheorie en de algebraïsche meetkunde. De hoofdidealen van de ring van de gehele getallen zijn de idealen (0), (2), (3), (5), (7), (11), ... De hoofdstelling van de rekenkunde veralgemeent naar de stelling van Lasker-Noether die ieder ideaal uitdrukt in een Noetherse commutatieve ring als de doorsnede van priemidealen, met de juiste veralgemeningen van priemmachten.

Priemidealen zijn de punten van algebro-meetkundige objecten, via de notie van het spectrum van een ring. De rekenkundige meetkunde profiteert ook van deze notie, en veel concepten bestaan zowel in de meetkunde als de getaltheorie. Factorisatie van vertakkingen van priemidealen, vertonen bijvoorbeeld bij het opheffen van een uitbreidingslichaam (in België: uitbreidingsveld), een fundamenteel probleem van de algebraïsche getaltheorie, enige gelijkenis met vertakking in de meetkunde.

Kunst en literatuur 
Priemgetallen hebben invloed uitgeoefend op veel kunstenaars en schrijvers. De Franse componist Olivier Messiaen gebruikte priemgetallen om zijn ametrische muziek via "natuurlijke fenomenen" te creëren. In werken zoals La Nativité du Seigneur (1935) en Quatre études de rythme (1949-50) maakte hij tegelijkertijd gebruik van motieven, waarvan de lengte werd gegeven door verschillende priemgetallen om zo onvoorspelbare ritmes te creëren: de priemgetallen 41, 43, 47 en 53 komen in een van zijn études voor. Volgens Messiaen werd deze manier van componeren "geïnspireerd door de bewegingen van de natuur, de bewegingen van vrije en ongelijke duur".

In zijn sciencefictionnovelle Contact, later omgewerkt tot de film met dezelfde naam, stelde de NASA-wetenschapper Carl Sagan voor dat priemgetallen gebruikt konden worden als een middel om met buitenaardse wezens te communiceren, een idee dat hij informeel in 1975 voor het eerst samen had ontwikkeld met de Amerikaanse astronoom Frank Drake.

Veel films weerspiegelen een populaire fascinatie voor de geheimen van de priemgetallen en de cryptografie: films zoals Cube, Sneakers, The Mirror Has Two Faces en A Beautiful Mind, waarvan de laatste gebaseerd is op de biografie door Sylvia Nasar van de wiskundige en Nobelprijswinnaar John Forbes Nash. Priemgetallen worden ook gebruikt als een metafoor voor eenzaamheid en isolement in de roman van Paolo Giordano De eenzaamheid van de priemgetallen, waarin priemgetallen worden afgeschilderd als de "buitenstaanders" onder de gehele getallen.

Opmerkelijke citaten 
"Wiskundigen hebben tot de dag van vandaag vergeefs geprobeerd enige orde te ontdekken in de rij van priemgetallen, en we hebben reden te geloven dat het een mysterie is waartoe de menselijke geest nooit zal doordringen." — Leonhard Euler

"God dobbelt misschien niet met het heelal, maar er is iets vreemds aan de hand met de priemgetallen." — Paul Erdős

Zie ook 
 Lijst van priemgetallen

Voetnoten

Externe link 
  : The PrimePages