Brontekst bekijken van Priemgetal

[[Afbeelding:Sieve_of_Eratosthenes_animation.gif|thumb|upright=1.2|De [[zeef van Eratosthenes]] kan gebruikt worden om priemgetallen op te sporen.]]

Een '''priemgetal''' is een [[natuurlijk getal]], groter dan 1,{{Refn|group=kleine-letter|Door de afspraak dat het getal 1 geen priemgetal is, kan onder andere de [[hoofdstelling van de rekenkunde]] eenvoudiger geformuleerd worden.}} 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 de [[getaltheorie]].

De eerste 30 priemgetallen zijn [[2 (getal)|2]], [[3 (getal)|3]], [[5 (getal)|5]], [[7 (getal)|7]], [[11 (getal)|11]], [[13 (getal)|13]], [[17 (getal)|17]], [[19 (getal)|19]], [[23 (getal)|23]], [[29 (getal)|29]], [[31 (getal)|31]], [[37 (getal)|37]], [[41 (getal)|41]], [[43 (getal)|43]], [[47 (getal)|47]], [[53 (getal)|53]], [[59 (getal)|59]], [[61 (getal)|61]], [[67 (getal)|67]], [[71 (getal)|71]], [[73 (getal)|73]], [[79 (getal)|79]], [[83 (getal)|83]], [[89 (getal)|89]], [[97 (getal)|97]], [[101 (getal)|101]], [[103 (getal)|103]], [[107 (getal)|107]], [[109 (getal)|109]] en [[113 (getal)|113]].<ref>{{Link OEIS|id=A000040}}</ref>

Priemgetallen werden reeds door de [[oude Grieken]] bestudeerd. Er zijn [[Oneindigheid|oneindig]] veel priemgetallen. Het [[bewijs (wiskunde)|bewijs]] hiervoor wordt gegeven door de [[stelling van Euclides]]. De oudste methode om priemgetallen te vinden is de [[zeef van Eratosthenes]].

Er is geen formule bekend die alle priemgetallen, maar geen [[samengesteld getal|samengestelde getallen]] oplevert. De verdeling van priemgetallen, dat wil zeggen, het [[statistiek|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 <math>n</math> een priemgetal is, omgekeerd evenredig is met het aantal cijfers, of de [[logaritme]] van <math>n</math>. 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 [[priemtweeling#vermoeden|vermoeden van de priemtweelingen]], dat zegt dat er oneindig veel priemgetaltweelingen (paren van priemgetallen, waarvan het [[Verschil (wiskunde)|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 [[ontbinden in priemfactoren|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&nbsp;425&nbsp;170 cijfers.<ref>{{en}}[http://www.mersenne.org/ Website Great Internet Mersenne Prime Search]</ref> In 2018 werd het tot nu toe grootste priemgetal ontdekt, dat volledig uitgeschreven uit 24&nbsp;862&nbsp;048 cijfers bestaat.<ref>[http://www.standaard.be/cnt/dmf20181228_04067298 ''We hebben een nieuw recordpriemgetal''], De Standaard, 28 december 2018</ref>

== 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 Griekenland|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 [[Grieken|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 [[Gottfried Wilhelm Leibniz|Leibniz]] en [[Leonhard Euler|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 <math>2^{2^n}+1</math> priem zijn (ze worden naar hem [[fermatgetal]]len genoemd) en hij verifieerde dit tot en met <math>n=4</math> (of <math>2^{16}+1</math>). Het volgende fermatgetal, <math>2^{32}+1</math>, 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 <math>2^p-1</math>, waarin <math>p</math> een priemgetal is. Dit type priemgetallen wordt naar hem [[mersennepriemgetal]]en genoemd.

Bij Eulers werk in de getaltheorie zaten vele resultaten met betrekking tot priemgetallen. Hij toonde aan dat de [[reeks (wiskunde)|oneindige reeks]] [[bewijs dat de som van de reciproquen van de priemgetallen divergeert|{{nowrap|1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...}}]] [[divergentie (wiskunde)|divergeert]].
In 1747 toonde hij aan dat de even [[perfect getal|perfecte getallen]] exact de gehele getallen van de vorm <math>2^{p-1}(2^p-1)</math> zijn, waar de tweede priemfactor een mersennepriemgetal is.

Aan het begin van de 19e eeuw, uitten [[Adrien-Marie Legendre|Legendre]] en [[Carl Friedrich Gauss|Gauss]] onafhankelijk van elkaar het vermoeden, dat als <math>x</math> naar [[oneindigheid|oneindig]] nadert, het aantal priemgetallen tot en met <math>x</math> asymptotisch naar <math>x/\ln(x)</math> nadert, waarin <math>\ln(x)</math> de [[natuurlijke logaritme]] van <math>x</math> is. Ideeën van Riemann in zijn [[Über die Anzahl der Primzahlen unter einer gegebenen Grösse|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 [[Jacques Hadamard|Hadamard]] als [[Charles-Jean de La Vallée Poussin|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 [[priemgetaltest]]en voor grote getallen gewerkt, waarbij zij zich vaak tot specifieke getalvormen hebben beperkt.
Hiertoe behoren onder andere de [[Pépin-test]]en voor fermatgetallen (1877), de [[Prothgetal|stelling van Proth]] (rond 1878) en de [[Lucas-Lehmertest voor mersennegetallen|Lucas-Lehmer-priemgetaltest]] (dateert oorspronkelijk uit 1856),<ref>[http://primes.utm.edu/notes/by_year.html het grootst bekende priemgetal naar jaar: een korte geschiedenis] [http://primes.utm.edu/curios/page.php?number_id=135 Prime Curios!: 17014..05727 (39-cijfers)]</ref> en de veralgemeende [[Algemene Lucas-Lehmertest|Lucas-priemgetaltest]]. Meer recente algoritmen zoals de [[Adleman-Pomerance-Rumely-priemgetaltest|APRT-CL]], het [[Elliptische kromme-primaliteitsbewijs|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)|RSA]]-cryptografie-algoritme.

Sinds 1951 zijn alle [[grootst bekende priemgetal]]len gevonden met behulp van [[computer]]s. 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.

== Hoofdstelling van de rekenkunde ==
{{Zie hoofdartikel|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
: <math>23244 = 2 \cdot 2 \cdot 3 \cdot 13 \cdot 149 = 2^2 \cdot 3 \cdot 13 \cdot 149\quad</math> (<math>2^2</math> 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 <math>n</math> als het product van priemgetallen
: <math>n=p_1\cdot p_2\cdot\ldots\cdot p_t</math>

heet het ontbinden van <math>n</math> in priemfactoren. Ook al zijn er verschillende [[algoritme]]n om een getal in priemfactoren te ontbinden, in het bijzonder voor grotere getallen, zij zullen allemaal dezelfde priemgetallen geven.

De [[verzameling (wiskunde)|verzameling]] van alle priemgetallen wordt wel aangeduid met <math>\mathbb{P}</math>.

=== Voorbeelden en eerste eigenschappen ===
[[Afbeelding:Prime rectangles.png|thumb|Illustratie waaruit blijkt dat 11 een priemgetal is, terwijl 12 dat niet is]]

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 [[decimaal|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 (wiskunde)|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 <math>6n-1</math> of <math>6n+1</math>, omdat alle andere getallen deelbaar zijn door 2 of 3. Alle priemgetallen groter dan <math>q</math> zijn van de [[primoriaal|vorm]] <math>qn+m</math>, waarbij <math>0<m<q</math> en <math>m</math> geen priemfactor gemeenschappelijk heeft met <math>q</math> of met <math>n</math>.  

Als <math>p</math> een priemgetal is en <math>p</math> deler is van een product <math>ab</math> van gehele getallen, dan is <math>p</math> deler van <math>a</math>, van <math>b</math> of van <math>a</math> en <math>b</math> 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.<ref>Gowers, 2002, pag. 118 "De schijnbaar willekeurige uitsluiting van 1 uit de definitie van een priemgetal ... drukt geen diep feit over getallen uit: maar bleek toevallig een nuttige conventie te zijn, die is overgenomen opdat er maar een manier zou zijn om een gegeven getal in priemgetallen te factoriseren."</ref><ref>[http://primes.utm.edu/notes/faq/one.html "Waarom is het getal een geen priemgetal?"]</ref>

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 [[Moritz Abraham Stern|Stern]] en Zeisel. [[Derrick Norman Lehmer]]s [[lijst van priemgetallen]] tot en met 10.006.721, die nog in 1956 werd herdrukt<ref>Riesel, 1994, p. 36.</ref> begon met 1 als het eerste priemgetal.<ref>Conway, Guy, pag. 129-130.</ref> 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 [[indicator (getaltheorie)|Euler-totiëntfunctie]], of de "som-van-de-delers-functie".<ref>"[http://primefan.tripod.com/Prime1ProCon.html "Argumenten voor en tegen de primaliteit van het getal 1]".</ref>

== Ontbinden in priemfactoren ==
De [[hoofdstelling van de rekenkunde]] zegt dat ieder [[Natuurlijk getal|natuurlijke getal]] groter dan 1 op één manier in [[Ontbinden in priemfactoren|priemfactoren is te ontbinden]], dat wil zeggen kan worden geschreven als het [[Product (wiskunde)|product]] van priemgetallen. Er zijn verschillende [[algoritme]]n om een getal <math>n</math> te ontbinden, zoals:
* uitprobeermethode<ref>[[Engels]]: [[:en:Trial division|Trial division]].</ref>
* [[Pollards p–1-methode]]
* [[algoritme van Lenstra]]
* [[Dixons factorisatiemethode]]

=== Uitprobeermethode ===
De eenvoudigste manier om een getal <math>n</math> in priemfactoren te ontbinden is te kijken welke getallen priemgetallen zijn en te controleren dat <math>n</math> hierdoor kan worden [[Delen|gedeeld]]. Deze manier is niet erg efficiënt. Hiervoor moet voor de priemgetallen <math>p</math>, van klein naar groot met de [[zeef van Eratosthenes]], die kleiner dan of gelijk zijn aan <math>\sqrt{n \ }</math>, worden gecontroleerd dat <math>n</math> door <math>p</math> kan worden gedeeld. Blijkt <math>n</math> door een bepaald priemgetal <math>p</math> te kunnen worden gedeeld, dan moet verder worden onderzocht welke volgende priemgetallen <math>q \le \sqrt{n/p \ }</math> er nog zijn, zodat <math>n/p</math> door <math>q</math> kan worden gedeeld, beginnend bij het priemgetal <math>p</math> en doorgaand tot ten hoogste <math>\sqrt{n/p \ }</math>. Dit moet zo worden voortgezet, totdat <math>n</math> volledig in priemgetallen is ontbonden.

==== Voorbeelden ====
* Bij het ontbinden van 98 in priemfactoren wordt in eerste instantie gekeken naar priemgetallen kleiner of gelijk aan <math>\sqrt{98 \ }</math>, dus kleiner dan 10. 98 kan door 2 worden gedeeld: {{nowrap|98 / 2 {{=}} 49}}. Daarna wordt naar priemgetallen <math>p</math> kleiner of gelijk aan <math>\sqrt{49} = 7</math> gekeken, zodat 49 door <math>p</math> kan worden gedeeld. Dan blijkt dat {{nowrap|49 {{=}} 7 · 7}}. Ontbonden in priemfactoren is {{nowrap|98 {{=}} 2 · 7 · 7}}.
* Als 143 ontbonden wordt in priemfactoren, wordt gekeken naar priemgetallen kleiner of gelijk aan <math>\sqrt{143}</math>, dus priemgetallen tot en met 11. Het blijkt dat 143 niet door 2, 3, 5 of 7, maar wel door 11 kan worden gedeeld, want {{nowrap|143 {{=}} 11 · 13}}. Het getal 13 is eveneens een priemgetal, dus ontbonden in priemfactoren is {{nowrap|143 {{=}} 11 · 13}}.

== Aantal priemgetallen ==
{{Zie hoofdartikel|Stelling van Euclides}}
Er zijn [[oneindige verzameling|oneindig]] veel priemgetallen. Het oudst bekende [[bewijs (wiskunde)|bewijs]] voor deze uitspraak, waaraan soms wordt gerefereerd als de [[stelling van Euclides]], wordt toegeschreven aan de [[Oude Griekenland|oud-Griekse]] wiskundige [[Euclides van Alexandrië|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:

<blockquote>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 samengestelde getallen 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)</blockquote>

De argumentie van Euclides verklaart dat als <math>p</math> het product is van een eindig aantal priemgetallen, het getal <math>p+1</math> 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 <math>p+1</math> 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 <math>p</math> is daarbij het product van al deze priemgetallen en er wordt geconcludeerd dat, omdat <math>p+1</math> niet deelbaar is door enig priemgetal, het zelf een priemgetal is, wat een tegenspraak inhoudt (citaat [[G.H. Hardy]]<ref>Hardy, 1908, pag. 122-123.</ref>). Dit voert lezers soms tot de onterechte conclusie, dat als <math>p</math> het [[primoriaal|product van de eerste <math>n</math> priemgetallen]] is, het getal <math>p+1</math> 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]] <math>p+1</math> is:

: <math>2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509</math>

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 [[reciproque]]n van alle priemgetallen resulteert in een [[divergentie (wiskunde)|divergerende]] [[reeks (wiskunde)|reeks]], en er dus meer dan eindig veel priemgetallen moeten zijn
: <math>\sum_{p \text{ prime}} \frac 1 p = \frac 12 + \frac 13 + \frac 15 + \frac 17 + \ldots = \infty</math>

Het bewijs hiervan is afkomstig van [[Leonhard Euler|Euler]]. Meer in het bijzonder: als <math>S(x)</math> de som aanduidt van de reciproquen van alle priemgetallen <math>p</math> met <math>p\le x</math>, dan geldt dat<ref>{{Aut|Eric. W. Weisstein}} [http://mathworld.wolfram.com/HarmonicSeriesofPrimes.html Harmonic Series of Primes], MathWorld, A Wolfram Web Resource</ref>
: <math>S(x)=\ln\ln x + O(1)</math> voor <math>x\to \infty\quad</math> (<math>O</math> staat voor de [[grote-O-notatie]]).

Een ander bewijs, gebaseerd op eigenschappen van [[Fermat-priemgetal]]len werd door [[Christian Goldbach|Goldbach]]<ref>[http://www.math.dartmouth.edu/~euler/correspondence/letters/OO0722.pdf brief] in het [[Latijn]] van Goldbach aan Euler, juli 1730.</ref> gegeven.
[[Ernst Kummer|Kummers]] bewijs is bijzonder elegant<ref>Ribenboim, 2004, pag. 4.</ref> en [[Harry Furstenberg]] geeft zijn [[bewijs van Furstenberg]] over de [[oneindigheid]] van het aantal priemgetallen met hulp van de algemene [[topologie]].<ref>Furstenberg, 1955</ref>

Niet alleen zijn er oneindig veel priemgetallen, de [[stelling van Dirichlet over rekenkundige rijen]] stelt dat in elke [[rekenkundige rij]] <math>a,a+q,a+2q,a+3q,\ldots</math> waarin de positieve gehele getallen <math>a</math> en <math>q</math> [[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.<ref>Ben J. Green, Terence Tao, arXiv, math.NT/0404188, The primes contain arbitrarily long arithmetic progressions (De priemgetallen bevatten willekeurig lange rekenkundig rijen), [[Annals of Mathematics]], vol = 167, 2008, pag = 481-547.</ref>

== Verificatie van priemgetallen ==
{{Zie hoofdartikel|Priemgetaltest}}
Om priemgetallen te gebruiken, is [[verificatiebeginsel|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 [[zeeftheorie|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 10<sup>7</sup>.<ref>Lehmer, 1909.</ref>

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 <math>n</math>, deel <math>n</math> door alle getallen <math>m</math>, kleiner dan of gelijk aan de [[wortel (wiskunde)|wortel]] van het getal, <math>n</math>. 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 <math>m</math> 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 <math>n</math> in de buurt van <math>n/(\ln(n)-1)</math>. Om <math>n</math> te controleren met de priemgetaltest is de grootste priemfactor die nodig is iets minder dan <math>\scriptstyle\sqrt{n}</math> en het aantal van zulke priemfactorkandidaten zou dicht in de buurt liggen van <math>\sqrt{n}/(\ln\sqrt{n} - 1)</math>. Dit aantal neemt steeds langzamer toe naarmate <math>n</math> groter wordt, maar omdat er belangstelling is voor grote waarden van <math>n</math>, is de telling ook groot: voor <math>n=10^{20}</math> bedraagt zij 450 miljoen.

Moderne priemgetaltestalgoritmen kunnen worden onderverdeeld in twee hoofdklassen, [[deterministisch algoritme|deterministische-]] en [[probabilistische algoritme|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 <math>a</math>, dat de "getuige" wordt genoemd, en checken vervolgens een formule, waarbij zowel de getuige als het potentiële priemgetal <math>n</math> voorkomen. Na een aantal iteraties, verklaren zij dat of <math>n</math> "zeker samengesteld" of "[[waarschijnlijk priem]]" is. De [[Priemtest van Fermat|Fermatpriemgetaltest]] beroept zich bijvoorbeeld op de [[kleine stelling van Fermat]] (zie hierboven). Als dus
: <math>a^p-1 \pmod p \ne 1</math>,

dan is <math>p</math> zeker samengesteld. <math>p</math> kan echter ook samengesteld zijn, als <math>a^p-1 \pmod p = 1</math> voor alle getuigen <math>a</math>, namelijk als <math>p</math> een [[Carmichael-getal]] is. In het algemeen zullen samengestelde getallen die, ongeacht de gekozen getuige, voor de desbetreffende test "waarschijnlijk priem" worden verklaard, [[pseudopriemgetal]]len 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 <math>n</math>, het getal waarop getest wordt, en voor probabilistische algoritmen, het aantal <math>k</math> van de uitgevoerde testen.

:{| class="wikitable"
! Test
! Ontwikkeld in
! Deterministisch
! Lopende tijd
! Notities
|-
| [[AKS-test]]
| 2002
| Ja
| <math>O(\log^{6+\varepsilon}(n))</math>
|
|-
| [[Priemtest van Fermat]]
|
| Nee
| <math>O(k\cdot\log^2(n)\cdot\log\log(n)\cdot\log\log\log(n))</math>
| faalt voor [[Carmichael-getal]]len
|-
| [[Algemene Lucas-Lehmertest|Lucas-priemgetaltest]]
|
| Ja
|
| vereist factorisatie van <math>n-1</math>
|-
| [[Solovay-Strassen-priemgetaltest]]
| 1977
| Nee, foutwaarschijnlijkheid <math>2^{-k}</math>
| <math>O(k\cdot\log^3(n))</math>
|
|-
| [[Miller-Rabin-priemgetaltest]]
| 1980
| Nee, foutwaarschijnlijkheid <math>4^{-k}</math>
| <math>O(k\cdot\log^2(n)\cdot\log\log(n)\cdot\log\log\log(n))</math>
|
|-
| [[Elliptische kromme-priemgetaltest]]
| 1977
| Nee
| <math>O(\log^{5+\varepsilon}(n))</math>
| heuristische lopende tijd
|}

=== Bijzondere priemgetallen ===
[[Afbeelding:Pentagon construct.gif|thumb|[[Constructie met passer en liniaal]] van een [[regelmatige veelhoek|regelmatige vijfhoek]]. 5 is een [[fermat-priemgetal]].]]

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 <math>2^p-1</math>, waarin <math>p</math> een priemgetal is, staan bekend als [[mersennepriemgetal]]len. Hun belang ligt in het feit dat er relatief snelle priemgetaltestalgoritmen voor het testen van mersennepriemgetallen bestaan.

Priemgetallen van de vorm <math>2^{2^n}+1</math> staan bekend als [[Fermat-priemgetal]]len; een [[regelmatige veelhoek|regelmatige <math>n</math>-hoek]] is [[dan en slechts dan als|dan en slechts dan]] [[Constructie met passer en liniaal|construeerbaar met passer en liniaal]] als
: <math>n=2^i\cdot m</math>,
waarin <math>m</math> een product van enig aantal verschillende Fermat-priemgetallen en <math>i</math> een willekeurig natuurlijk getal is, inclusief nul. Er zijn slechts vijf Fermat-priemgetallen bekend: 3, 5, 17, 257 en 65.537.

Priemgetallen <math>p</math>, waarbij <math>2p+1</math> ook een priemgetal is, staan bekend als de [[Sophie Germainpriemgetal]]len. Een priemgetal <math>p</math> noemt men ''[[primoriaal priemgetal|primoriaal]]'' of ''priem-factoriaal'', indien voor enig getal <math>n</math> dit priemgetal de vorm heeft
: <math>p=n\#\pm 1</math>, 
waarin [[primoriaal|<math>n\#</math>]] staat voor het product <math>2\cdot 3\cdot 5\cdot 7\cdot\ldots</math> van alle priemgetallen <math>\le n</math>. Een priemgetal wordt ''[[factoriaal priemgetal|factoriaal]]'' genoemd als het van de vorm <math>n!\pm 1</math> is. Het is niet bekend of er oneindig veel primoriale of factoriale priemgetallen zijn.

=== 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 oktober 2024) is het getal 2<sup>136&nbsp;279&nbsp;841</sup>-1 en bestaat uit 41&nbsp;024&nbsp;320 cijfers.<ref>{{Citeer web |url=https://www.mersenne.org/primes/?press=M136279841 |titel=Mersenne Prime Number discovery - 2<sup>136279841</sup>-1 is Prime! |bezochtdatum=2024-10-22 |achternaam= |voornaam= |auteurlink= |medeauteurs= |datum=2024-10-21 |formaat= |werk= |uitgever= |paginas= |taal=en |archiefurl= |archiefdatum= |dodeurl= |citaat= }}</ref> De volgende tabel geeft de grootste bekende priemgetallen van de genoemde soorten:

:{| class="wikitable" border="1"
! Priemgetal
! Aantal decimale cijfers
! Soort
! Datum
! Gevonden door
|-
| 2<sup>136&nbsp;279&nbsp;841</sup> − 1
| 41&nbsp;024&nbsp;320
| mersennepriemgetal
| 12 oktober 2024
| Luke Durant (Gimps)
|-
| 19&nbsp;249 × 2<sup>13&nbsp;018&nbsp;586</sup> + 1
| 3&nbsp;918&nbsp;990
| niet een mersennepriemgetal ([[Proth-getal]])
| 26 maart 2007
| [[Seventeen or Bust]]
|-
| 150&nbsp;209! + 1
| 712&nbsp;355
| factoriaal priemgetal
| oktober 2012
| PrimeGrid
|-
| 1&nbsp;098&nbsp;133# - 1
| 476&nbsp;311
| [[primoriaal]] priemgetal
| maart 2012
| PrimeGrid
|-
| 3&nbsp;756&nbsp;801&nbsp;695&nbsp;685 × 2<sup>666&nbsp;669</sup> ± 1
| 200&nbsp;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 <math>k</math> met <math>256^k</math> te vermenigvuldigen en vervolgens te zoeken naar mogelijke priemgetallen binnen het [[interval (wiskunde)|interval]] <math>[256^k n + 1,\ 256^k(n+1)-1]</math>.

De [[Electronic Frontier Foundation]] heeft in 2009 een prijs van 100.000 [[Amerikaanse dollar|dollar]] toegekend aan [[GIMPS|Great Internet Mersenne Prime Search (GIMPS)]] voor het als eerste ontdekken van een priemgetal dat ten minste uit 10 miljoen cijfers bestaat.<ref>[http://www.eff.org/press/archives/2009/10/14-0 Record 12-Million-Digit Prime Number Nets $100,000, Electronic Frontier Foundation]</ref> 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 (wiskunde)|verzameling]] van [[diofantische vergelijking]]en in 9 variabelen en een parameter met de volgende eigenschap: de parameter is [[dan en slechts dan als|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.

== Verdeling  ==
{{Zie hoofdartikel|Priemgetalstelling}}
[[Afbeelding:Ulam 1.png|200px|thumb|[[Ulam-spiraal]]. Zwarte pixels tonen 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 [[natuurlijk getal|natuurlijke getallen]] is (tot dusver) onvoorspelbaar, ook al zijn er wetten (zoals de [[priemgetalstelling]] en het [[postulaat van Bertrand]]), die hun gemiddelde verdeling regeren.<ref>Erica Klarreich, [http://empslocal.ex.ac.uk/people/staff/mrwatkin//zeta/ns111100.htm Prime Time], New Scientist, 11 november 2000</ref> [[Leonhard Euler]] sprak hierover meer dan 200 jaar geleden de volgende woorden:
<blockquote> 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.<ref>Havil, 2003, pag. 63</ref></blockquote>

In 1975 merkte [[Don Zagier]] tijdens een lezing het volgende op
<blockquote> 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.<ref>Havil, 2003, pag. 171</ref> </blockquote>

Euler merkte op dat de functie <math>n^2+n+41</math> priemgetallen geeft voor <math>n<40</math> (maar niet noodzakelijkerwijs voor een grotere <math>n</math>), een opmerkelijk feit, dat bij nadere beschouwing tot diepe [[algebraïsche getaltheorie]], meer specifiek de [[Heegner-getal]]len, leidt. De [[spiraal van Ulam]] toont alle natuurlijke getallen op een spiraalachtige manier. Verrassend genoeg clusteren priemgetallen op bepaalde diagonalen, maar niet op andere.<ref>{{Aut|Weisstein, Eric W.}} "[http://mathworld.wolfram.com/PrimeSpiral.html Prime Spiral.]" MathWorld--A Wolfram Web Resource</ref>

=== Aantal priemgetallen onder een gegeven aantal ===
{{Zie hoofdartikel|Priemgetal-telfunctie}}
[[Afbeelding:PrimeNumberTheorem.png|thumb|200px|{{legenda-lijn|2px solid #0101ff|<math>\pi(n)</math>}}{{legenda-lijn|2px solid #0fff0f|<math>n/\ln(n)</math>}}{{legenda-lijn|2px solid #ff2525|[[logaritmische integraalfunctie]]}}]]

De ''priemgetal-telfunctie'' <math>\pi(n)</math> wordt gedefinieerd als het aantal priemgetallen tot en met <math>n</math>. Bijvoorbeeld: <math>\pi(11)=5</math>, aangezien er vijf priemgetallen kleiner dan of gelijk aan 11 zijn. Er zijn bekende [[algoritme]]n om exacte waarden van <math>\pi(n)</math> sneller te berekenen dan het mogelijk is om het priem zijn van elk getal tot en met <math>n</math> te berekenen. Waarden zo groot als <math>\pi(10^{20})</math> kunnen met moderne computers snel en nauwkeurig worden berekend.

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

Als <math>n</math> een positief geheel getal groter dan 1 is, bestaat er altijd een priemgetal <math>p</math>, zodanig dat <math>n<p<2n</math> ([[postulaat van Bertrand]]).

=== Hiaten ===
{{Zie hoofdartikel|Priemgetalhiaat}}

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 <math>n</math> groter dan 1 is de rij (voor een uitleg over de notatie <math>n!</math> lees het artikel [[Faculteit (wiskunde)|faculteit]])
: <math>n!+2,n!+3,\ldots, n!+n</math>
een rij van <math>n-1</math> opeenvolgende samengestelde gehele getallen, omdat
: <math>n! + m = m \cdot (n!/m + 1) = m \cdot [(1 \cdot 2 \cdot\ldots\cdot (m - 1) \cdot (m + 1)\cdot \ldots \cdot n) + 1]</math>
samengesteld is voor elke <math>2\le m \le n</math>.

Aan de andere kant kunnen priemgetalhiaten ook willekeurig klein worden in verhouding tot de priemgetallen: het quotiënt
: <math>(p_{i + 1} - p_i)/p_i</math>,

waarin <math>p_i</math> het <math>i</math>-de priemgetal aanduidt (dat wil zeggen dat <math>p_1=2,\ p_2=3,</math> enz.), [[rij (wiskunde)|benadert]] nul als <math>i</math> naar [[oneindigheid|oneindig]] nadert.

== Open vragen ==
=== Riemann-hypothese ===
{{Zie hoofdartikel|Riemann-hypothese}}

De riemann-hypothese is een van de oudste [[vermoeden]]s 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]] <math>s</math> met het [[Reëel deel|reële deel]] groter dan 1 gedefinieerd is als:
: <math>\zeta(s)=\sum_{n=1}^\infin \frac{1}{n^s} = \prod_{p\text{ priem}} \frac{1}{1-p^{-s}}</math>

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 rij]]en:
: <math>\zeta(1) = \sum_{n=1}^\infin \frac{1}{n} = \prod_{p\text{ priem}} \frac{1}{1-p^{-1}} = \infty</math>
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,
: <math>\zeta(2) = \prod_{p\text{ priem}} \frac{1}{1-p^{-2}}= \frac{\pi^2}{6}</math>

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 (signaal)|ruis]]. De [[priemgetalstelling]]  zegt dat ongeveer <math>1/\log x</math> van alle getallen kleiner dan <math>x</math> priemgetallen zijn, maar de riemann-hypothese stelt dat de asymptotische verdeling van priemgetallen ook geldig is voor veel kortere intervallen over de vierkantswortel van <math>x</math>, voor de intervallen in de buurt van <math>x</math>. 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 <math>n^2+1</math> 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-priemgetal]]len<ref>Caldwell, Chris, [http://primes.utm.edu/top20/page.php?id=48 ''De top twintig: lucas-getal''] op de [[Prime Pages]].</ref> en oneindig veel [[mersennepriemgetal]]len bestaan, maar men vermoedt dat het aantal [[fermat-priemgetal]]len niet oneindig is.<ref>zie bijvoorbeeld Guy, 1981, probleem A3, pag. 7-8.</ref> Het is niet bekend of er oneindig veel priem-[[euclides-getal]]len bestaan.

Een aantal vermoedens heeft betrekking op aspecten van de verdeling van priemgetallen. Men vermoedt dat er oneindig veel [[priemtweeling]]en, paren van priemgetallen met verschil 2, ([[Problemen van Landau|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 <math>n</math>, er oneindig veel paren van opeenvolgende priemgetallen bestaan, die van elkaar met <math>2n</math> 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 <math>n^2</math> en <math>(n+1)^2</math> bestaat voor elk positief geheel getal <math>n</math>. Dit laatste vermoeden wordt geïmpliceerd door het sterkere [[vermoeden van Cramér]].

Andere vermoedens hebben betrekking op [[additieve getaltheorie|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 vermoeden van Goldbach|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 [[Verenigd Koninkrijk|Britse]] wiskundige [[G. H. Hardy]] er trots op werk te doen, dat absoluut geen enkele militaire betekenis had<ref>Hardy, 1940 "Niemand heeft nog een militaire doel ontdekt dat gediend door de getaltheorie of [[relativiteitstheorie]], en het lijkt voor vele jaren onwaarschijnlijk dat iemand dat zal doen"</ref> 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 [[hashtabel]]len en [[toevalsgenerator|pseudowillekeurigegetallengeneratoren]].

Sommige [[rotormachine]]s 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 ===
{{Zie hoofdartikel|Modulair rekenen}}
''Modulair rekenen'' is een variant van de gebruikelijke rekenkunde. Bij het "rekenen modulo" een vast getal <math>n</math> vinden de berekeningen plaats in de [[eindige verzameling]] <math>\overline{n}=\{1,2,\ldots, n-1\}</math> en worden resultaten steeds gereduceerd met zoveel veelvouden van <math>n</math> dat het eindresultaat in deze verzameling ligt. 

In het algemeen is echter niet mogelijk om in deze setting te [[delen]]. Voor bijvoorbeeld <math>n=6</math> heeft de vergelijking
: <math>3x\equiv 2 \pmod 6</math>
geen oplossing <math>x\in \overline{n}</math>, die het analogon zou zijn van 2/3. Het onderscheidend kenmerk is dat in de modulaire rekenkunde [[dan en slechts dan als|dan en slechts dan]] deling modulo <math>n</math> mogelijk is als <math>n</math> een priemgetal is. Zo heeft de vergelijking
: <math>3x\equiv 2 \pmod 7</math>
de unieke oplossing <math>x=3</math>. Op equivalent wijze is <math>n</math> dan en slechts dan een priemgetal, als alle gehele getallen <math>2\le m\le n-1</math> [[relatief priem]] zijn ten opzichte van <math>n</math>, dat wil zeggen dat hun [[grootste gemene deler]] gelijk is aan 1. 

De verzameling <math>\overline{n}</math> met optellen en vermenigvuldigen wordt aangeduid als <math>\Z/n\Z</math>. Sommige stellingen kunnen op een abstracte manier worden afgeleid uit de beschouwing van <math>\Z/p\Z</math>. De [[kleine stelling van Fermat]] bijvoorbeeld, waarin wordt gesteld dat <math>a^p-a</math> voor elk [[geheel getal]] <math>a</math> deelbaar is door <math>p</math>, kan met behulp van deze worden bewezen. Een gevolg hiervan is het volgende: als <math>p</math> een priemgetal anders dan 2 en 5 is, dan is <math>1/p</math> een [[repeterende breuk]], waarvan de periode gelijk is aan <math>p-1</math> of een deler van <math>p-1</math>. De breuk <math>1/p</math>, uitgedrukt met het grondtal <math>q</math> (in plaats van 10), heeft dezelfde eigenschap, op voorwaarde dat <math>p</math> geen priemfactor van <math>q</math> is. De [[stelling van Wilson]] zegt dat een geheel getal <math>p>1</math> dan en slechts dan een priemgetal is, als de [[Faculteit (wiskunde)|faculteit]] <math>(p-1)!+1</math> deelbaar is door <math>p</math>. Bovendien is een geheel getal <math>n>4</math> dan en slechts dan een samengesteld getal, als <math>(n-1)!</math> deelbaar is door <math>n</math>.

=== Groepentheorie ===
Veel wiskundige deelgebieden maken intensief gebruik van priemgetallen. Een voorbeeld uit de theorie van de [[eindige groep]]en zijn de [[stellingen van Sylow]]: als <math>G</math> een eindige [[groep (wiskunde)|groep]] is en <math>p^n</math> de [[p-adische orde|hoogste macht van het priemgetal]] <math>p</math> is, die de [[orde (groepentheorie)|orde]] van <math>G</math> deelt, dan heeft <math>G</math> een [[deelgroep]] van orde <math>p^n</math>. Elke groep met een priemorde is dus [[cyclische groep|cyclisch]] ([[stelling van Lagrange (groepentheorie)|stelling van Lagrange]]).
Als <math>G</math> een eindige groep is en <math>p</math> een priemgetal is, dat de orde van <math>G</math> deelt, dan bevat <math>G</math> een [[element (wiskunde)|element]] van orde <math>p</math> ([[stelling van Cauchy]]).

=== Publiekesleutelcryptografie ===
{{Zie hoofdartikel|asymmetrische cryptografie}}
Verschillende publiekesleutelcryptografie-algoritmen, zoals [[RSA (cryptografie)|RSA]] of het [[Diffie-Hellman-sleuteluitwisselingsprotocol]] zijn gebaseerd op zeer grote priemgetallen (die bijvoorbeeld uit 512 [[bit (eenheid)|bits]] bestaan). Deze algoritmen vertrouwen op het feit dat het veel gemakkelijker is om twee heel grote getallen, <math>x</math> en <math>y</math> met elkaar te vermenigvuldigen, met als resultaat <math>p</math>, dan om het omgekeerde te doen, en uit <math>p</math> de waarde van <math>x</math> en <math>y</math> terug te rekenen, indien deze <math>x</math> en <math>y</math> [[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 [[cicade]]n van het geslacht ''[[Magicicada]]''<ref>{{aut|Goles, E.}}, {{aut|Schulz, O.}} en {{aut|M. Markus}} (2001). "Prime number selection of cycles in a predator-prey model ", Complexity 6 (4): 33-38</ref> lijkt te worden gebruikt. Deze insecten brengen het grootste deel van hun leven als [[larve]]n 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<ref>R.A. Paulo Campos, Viviane M. de Oliveira, Ronaldo Giro, en Douglas S. Galvão. [http://link.aps.org/abstract/PRL/v93/e098107 zie hier], De opkomst van priemgetallen als gevolg van de Evolutionaire Strategie, [[Physical Review Letters|Phys. Rev Lett.]], vol= 93, 2004, pages 98-107</ref> 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.<ref>[[The Economist]], [http://economist.com/PrinterFriendly.cfm?Story_ID=2647052 zie hier], Invasion of the Brood, 6 mei 2004</ref> 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 [[kwantumsysteem|kwantumsystemen]].<ref>Ivars Peterson, [[MAA Online]], [http://www.maa.org/mathland/mathtrek_6_28_99.html zie hier], De terugkeer van Zeta, 28 juni 1999</ref>

=== Priemgetallen in de techniek ===
Bij de aandrijving met behulp van kamwielen, zoals toegepast in [[windmolen]]s, 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.

== Eigenschappen ==
* Als <math>p</math> een priemgetal is en <math>p</math> deelt een product <math>ab</math> van natuurlijke getallen, dan is <math>p</math> een deler van <math>a</math> of van <math>b</math> (zie ook [[Priemgetal#Ring theorie|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 (wiskunde)|ring]] <math>\Z/n\Z</math> (zie [[modulair rekenen]]) is een [[Lichaam (Ned) / Veld (Be)|lichaam]] (in België: veld) ofwel [[eindig lichaam]] dan en slechts dan als <math>n</math> een priemgetal is. Anders gezegd: <math>n</math> is een priemgetal dan en slechts dan als de [[Indicator (getaltheorie)|totiëntfunctie]] <math>\varphi(n)=n-1</math>.
* Als <math>p</math> een priemgetal is en <math>a</math> is een willekeurig geheel getal, dan is <math>a^p-a</math> deelbaar door <math>p</math> ([[kleine stelling van Fermat]]).
* Als <math>p</math> een priemgetal is anders dan 2 en 5, dan is <math>1/p</math> altijd een [[repeterende breuk]], met een periode van <math>p-1</math> of een deler van <math>p-1</math>. Deze kan direct van de [[kleine stelling van Fermat]] afgeleid worden. <math>1/p</math> uitgedrukt in een ander grondtal <math>q</math> (dus anders dan grondtal 10) heeft het vergelijkbare effect, gegeven dat <math>p</math> geen priemfactor is van <math>q</math> (zie [[repeterende breuk]] voor enkele interessante eigenschappen).
* Een geheel getal <math>p>1</math> is een priemgetal dan en slechts dan als <math>(p-1)!+1</math> deelbaar is door <math>p</math> ([[stelling van Wilson]]); hierbij staat het uitroepteken voor de [[faculteit (wiskunde)|faculteit]]. Omgekeerd, een geheel getal <math>n>4</math> is samengesteld dan en slechts dan als <math>(n-1)!</math> deelbaar is door <math>n</math>.
* Als <math>n</math> een positief geheel getal is, dan is er altijd een priemgetal <math>p</math> met  <math>n<p\le 2n</math> ([[Postulaat van Bertrand]]).
* Sommering van de omgekeerden van alle priemgetallen resulteert in een divergente [[reeks (wiskunde)|reeks]]. Meer precies, als <math>S(x)</math> de som van de omgekeerden van alle priemgetallen <math>p</math> is met <math>p\le x</math>, dan <math>S(x)=O(\ln\ln x)</math> voor <math>x\to \infty</math> (zie [[Grote-O-notatie]]).
* Alle priemgetallen hebben de vorm <math>6n+1</math> of <math>6n-1</math>, met als enige uitzonderingen 2 en 3, omdat de andere mogelijkheden alle deelbaar zijn door 2 of 3.
* Voor ieder priemgetal <math>p>2</math>, bestaat er een [[natuurlijk getal]] <math>n</math> zodat <math>p=4n\pm 1</math>.
* Voor ieder priemgetal <math>p>3</math>, bestaat er een natuurlijk getal <math>n</math> zodat <math>p=6n\pm 1</math>.
* Voor ieder priemgetal <math>p>3</math>, bestaat er een natuurlijk getal <math>n</math> zodat <math>p=24n+ 1</math>.
* De [[Karakteristiek (wiskunde)|karakteristiek]] van ieder lichaam (in België: veld) is nul of een priemgetal.
* Als <math>G</math> een eindige [[groep (wiskunde)|groep]] is en <math>p^n</math> is de hoogste macht van het priemgetal <math>p</math> dat de orde van <math>G</math> deelt, dan heeft <math>G</math> een subgroep van orde <math>p^n</math> ([[Stellingen van Sylow]]).
* Als <math>p</math> een priemgetal is en <math>G</math> is een groep met <math>p^n</math> elementen, dan bevat <math>G</math> een element van de orde <math>p</math>.
* De [[priemgetalstelling]] zegt dat het aantal priemgetallen kleiner dan <math>x</math> asymptotisch <math>x/\ln(x)</math> nadert.

== Onbeantwoorde vragen ==
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-priemgetal]]len?
* Is er een priemgetal tussen <math>n^2</math> en <math>(n+1)^2</math> voor elke <math>n>0</math>?
* Zijn er oneindig veel priemgetallen van de vorm <math>n^2+1</math>?
* Is het mogelijk een getal efficiënt (dat wil zeggen in [[polynomiale tijd]]) in [[priemfactor]]en te [[Factorisatie|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 [[Lichaam (Ned) / Veld (Be)#Deellichaam|deellichaam]] van een lichaam (in België: veld) <math>F</math>. Het is ofwel <math>\Q</math> of het [[Eindig lichaam (Ned) / Eindig veld (Be)|eindige lichaam]] met <math>p</math> 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 (wiskunde)|knoop]] die niet kan worden geschreven als de [[verbonden som]] van twee [[Triviale knoop|triviale knopen]]. Elke knoop kan uniek worden uitgedrukt als een verbonden som van priemknopen.<ref>{{de}} H Schubert. [https://books.google.nl/books/about/Die_Eindeutige_Zerlegbarkeit_Eines_Knote.html?id=ErRvQgAACAAJ&redir_esc=y Die Eindeutige Zerlegbarkeit eines Knotens in Primknoten], 1949. op [[Google Books]]</ref><ref>{{de}} H Schubert voor de Heidelberger Akademie der Wissenschaften. Die eindeutige Zerlegbarkeit eines Knotens in Primknoten, 1949. Math.-Nat. Kl., p 57–104</ref>  [[Priemmodel]]len en [[priem 3-variëteit]]en zijn andere voorbeelden van dit type.

=== Ringtheorie ===
In de [[ringtheorie]] beschouwt men als priemelement van een [[ring (wiskunde)|ring]] het element <math>p</math> dat de eigenschap heeft dat voor willekeurige [[element (wiskunde)|elementen]] <math>a</math> en <math>b</math> geldt dat wanneer <math>a \cdot b</math> deelbaar is door <math>p</math>, er ''moet'' gelden dat <math>a</math> of <math>b</math> deelbaar is door <math>p</math> (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 ===
{{Zie hoofdartikel|Priemideaal}}
In de [[ringtheorie]] wordt de notie van getal in het algemeen vervangen door die van een [[ideaal (ringtheorie)|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 ring|Noetherse]] [[commutatieve ring]] als de doorsnede van [[priemideaal|priemidealen]], met de juiste veralgemeningen van [[priemmacht]]en.<ref>Eisenbud, 1995, paragraaf 3.3</ref>

Priemidealen zijn de punten van [[algebraïsche meetkunde|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 [[Splitsen van priemidealen in Galois-uitbreidingen|vertakkingen]] van priemidealen, vertonen bijvoorbeeld bij het opheffen van een [[Lichaamsuitbreiding (Ned) / Velduitbreiding (Be)|uitbreidingslichaam]] (in België: uitbreidingsveld), een fundamenteel probleem van de algebraïsche getaltheorie, enige gelijkenis met [[vertakte dekking|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".<ref>Hill, 1995.</ref>

In zijn [[sciencefiction]]novelle ''[[Contact (boek)|Contact]]'', later omgewerkt tot de [[Contact (film)|film met dezelfde naam]], stelde de [[NASA]]-wetenschapper [[Carl Sagan]] voor dat priemgetallen gebruikt konden worden als een middel om met [[buitenaards leven|buitenaardse wezens]] te communiceren, een idee dat hij informeel in 1975 voor het eerst samen had ontwikkeld met de Amerikaanse astronoom [[Frank Drake]].<ref>[[Carl Pomerance]], [http://www.math.dartmouth.edu/~carlp/PDF/extraterrestrial.pdf Priemgetallen en de speurtocht naar buitenaardse intelligentie].</ref>

Veel films weerspiegelen een populaire fascinatie voor de geheimen van de priemgetallen en de cryptografie: films zoals ''[[Cube (film)|Cube]]'', ''[[Sneakers (film)|Sneakers]]'', ''[[The Mirror Has Two Faces]]'' en ''[[A Beautiful Mind (film)|A Beautiful Mind]]'', waarvan de laatste gebaseerd is op de biografie door [[Sylvia Nasar]] van de wiskundige en Nobelprijswinnaar [[John Forbes Nash]].<ref>[https://web.archive.org/web/20151009135943/http://www.musicoftheprimes.com/films.htm De muziek van priemgetallen], [[Marcus du Sautoy]]s selectie van films over priemgetallen.</ref> 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|Paul Erdős]]''

{{Appendix||2=
==Noten==
{{References|group=kleine-letter}}
==Bronnen==
{{References||2}}
}}

== Externe link ==
* {{en}} {{Aut|Chris K. Caldwell}}: [https://primes.utm.edu/ The PrimePages]

{{Navigatie bijzondere getallen}}
{{Commonscat|Prime numbers}}

[[Categorie:Priemgetal| ]]