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 de getaltheorie.

De zeef van Eratosthenes kan gebruikt worden om priemgetallen op te sporen.

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.

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 $n$ een priemgetal is, omgekeerd evenredig is met het aantal cijfers, of de logaritme van $n$. 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.

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 $2^{2^{n}}+1$ priem zijn (ze worden naar hem fermatgetallen genoemd) en hij verifieerde dit tot en met $n=4$ (of $2^{16}+1$). Het volgende fermatgetal, $2^{32}+1$, 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 $2^{p}-1$, waarin $p$ 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 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ... divergeert. In 1747 toonde hij aan dat de even perfecte getallen exact de gehele getallen van de vorm $2^{p-1}(2^{p}-1)$ 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 $x$ naar oneindig nadert, het aantal priemgetallen tot en met $x$ asymptotisch naar $x/\ln(x)$ nadert, waarin $\ln(x)$ de natuurlijke logaritme van $x$ 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.

Hoofdstelling van de rekenkunde

Zie hoofdstelling van de rekenkunde voor het hoofdartikel over dit onderwerp.

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

$23244=2\cdot 2\cdot 3\cdot 13\cdot 149=2^{2}\cdot 3\cdot 13\cdot 149\quad$ ($2^{2}$ 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 $n$ als het product van priemgetallen

$n=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{t}$

heet het ontbinden van $n$ 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 $\mathbb {P}$.

Voorbeelden en eerste eigenschappen

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

Als $p$ een priemgetal is en $p$ deler is van een product $ab$ van gehele getallen, dan is $p$ deler van $a$, van $b$ of van $a$ en $b$ 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 ieder natuurlijke 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 $n$ te ontbinden, zoals:

• uitprobeermethode
• Pollards p–1-methode
• algoritme van Lenstra
• Dixons factorisatiemethode

Uitprobeermethode

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

Voorbeelden

• Bij het ontbinden van 98 in priemfactoren wordt in eerste instantie gekeken naar priemgetallen kleiner of gelijk aan ${\sqrt {98\ }}$, dus kleiner dan 10. 98 kan door 2 worden gedeeld: 98 / 2 = 49. Daarna wordt naar priemgetallen $p$ kleiner of gelijk aan ${\sqrt {49}}=7$ gekeken, zodat 49 door $p$ kan worden gedeeld. Dan blijkt dat 49 = 7 · 7. Ontbonden in priemfactoren is 98 = 2 · 7 · 7.
• Als 143 ontbonden wordt in priemfactoren, wordt gekeken naar priemgetallen kleiner of gelijk aan ${\sqrt {143}}$, 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 143 = 11 · 13. Het getal 13 is eveneens een priemgetal, dus ontbonden in priemfactoren is 143 = 11 · 13.

Aantal priemgetallen

Zie Stelling van Euclides voor het hoofdartikel over dit onderwerp.

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 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)

De argumentie van Euclides verklaart dat als $p$ het product is van een eindig aantal priemgetallen, het getal $p+1$ 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 $p+1$ 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 $p$ is daarbij het product van al deze priemgetallen en er wordt geconcludeerd dat, omdat $p+1$ 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 $p$ het product van de eerste $n$ priemgetallen is, het getal $p+1$ 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 $p+1$ is:

$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\cdot 509$

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

$\sum _{p{\text{ prime}}}{\frac {1}{p}}={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\ldots =\infty$

Het bewijs hiervan is afkomstig van Euler. Meer in het bijzonder: als $S(x)$ de som aanduidt van de reciproquen van alle priemgetallen $p$ met $p\leq x$, dan geldt dat

$S(x)=\ln \ln x+O(1)$ voor $x\to \infty \quad$ ($O$ 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 $a,a+q,a+2q,a+3q,\ldots$ waarin de positieve gehele getallen $a$ en $q$ 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

Zie Priemgetaltest voor het hoofdartikel over dit onderwerp.

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 10⁷.

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 $n$, deel $n$ door alle getallen $m$, kleiner dan of gelijk aan de wortel van het getal, $n$. 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 $m$ 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 $n$ in de buurt van $n/(\ln(n)-1)$. Om $n$ te controleren met de priemgetaltest is de grootste priemfactor die nodig is iets minder dan $\scriptstyle {\sqrt {n}}$ en het aantal van zulke priemfactorkandidaten zou dicht in de buurt liggen van ${\sqrt {n}}/(\ln {\sqrt {n}}-1)$. Dit aantal neemt steeds langzamer toe naarmate $n$ groter wordt, maar omdat er belangstelling is voor grote waarden van $n$, is de telling ook groot: voor $n=10^{20}$ 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 $a$, dat de "getuige" wordt genoemd, en checken vervolgens een formule, waarbij zowel de getuige als het potentiële priemgetal $n$ voorkomen. Na een aantal iteraties, verklaren zij dat of $n$ "zeker samengesteld" of "waarschijnlijk priem" is. De Fermatpriemgetaltest beroept zich bijvoorbeeld op de kleine stelling van Fermat (zie hierboven). Als dus

$a^{p}-1{\pmod {p}}\neq 1$,

dan is $p$ zeker samengesteld. $p$ kan echter ook samengesteld zijn, als $a^{p}-1{\pmod {p}}=1$ voor alle getuigen $a$, namelijk als $p$ 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 $n$, het getal waarop getest wordt, en voor probabilistische algoritmen, het aantal $k$ van de uitgevoerde testen.

Test	Ontwikkeld in	Deterministisch	Lopende tijd	Notities
AKS-test	2002	Ja	$O(\log ^{6+\varepsilon }(n))$
Priemtest van Fermat		Nee	$O(k\cdot \log ^{2}(n)\cdot \log \log(n)\cdot \log \log \log(n))$	faalt voor Carmichael-getallen
Lucas-priemgetaltest		Ja		vereist factorisatie van $n-1$
Solovay-Strassen-priemgetaltest	1977	Nee, foutwaarschijnlijkheid $2^{-k}$	$O(k\cdot \log ^{3}(n))$
Miller-Rabin-priemgetaltest	1980	Nee, foutwaarschijnlijkheid $4^{-k}$	$O(k\cdot \log ^{2}(n)\cdot \log \log(n)\cdot \log \log \log(n))$
Elliptische kromme-priemgetaltest	1977	Nee	$O(\log ^{5+\varepsilon }(n))$	heuristische lopende tijd

Bijzondere priemgetallen

Constructie met passer en liniaal van een 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 $2^{p}-1$, waarin $p$ 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 $2^{2^{n}}+1$ staan bekend als Fermat-priemgetallen; een regelmatige $n$-hoek is dan en slechts dan construeerbaar met passer en liniaal als

$n=2^{i}\cdot m$,

waarin $m$ een product van enig aantal verschillende Fermat-priemgetallen en $i$ een willekeurig natuurlijk getal is, inclusief nul. Er zijn slechts vijf Fermat-priemgetallen bekend: 3, 5, 17, 257 en 65.537.

Priemgetallen $p$, waarbij $2p+1$ ook een priemgetal is, staan bekend als de Sophie Germainpriemgetallen. Een priemgetal $p$ noemt men primoriaal of priem-factoriaal, indien voor enig getal $n$ dit priemgetal de vorm heeft

$p=n\#\pm 1$,

waarin $n\#$ staat voor het product $2\cdot 3\cdot 5\cdot 7\cdot \ldots$ van alle priemgetallen $\leq n$. Een priemgetal wordt factoriaal genoemd als het van de vorm $n!\pm 1$ 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^{136 279 841}-1 en bestaat uit 41 024 320 cijfers. De volgende tabel geeft de grootste bekende priemgetallen van de genoemde soorten:

Priemgetal	Aantal decimale cijfers	Soort	Datum	Gevonden door
2136 279 841 − 1	41 024 320	mersennepriemgetal	12 oktober 2024	Luke Durant (Gimps)
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 $k$ met $256^{k}$ te vermenigvuldigen en vervolgens te zoeken naar mogelijke priemgetallen binnen het interval $[256^{k}n+1,\ 256^{k}(n+1)-1]$.

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.

Verdeling

Zie Priemgetalstelling voor het hoofdartikel over dit onderwerp.

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 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 $n^{2}+n+41$ priemgetallen geeft voor $n<40$ (maar niet noodzakelijkerwijs voor een grotere $n$), 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.

Aantal priemgetallen onder een gegeven aantal

Zie Priemgetal-telfunctie voor het hoofdartikel over dit onderwerp.

 $\pi (n)$

 $n/\ln(n)$

 logaritmische integraalfunctie

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

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

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

Hiaten

Zie Priemgetalhiaat voor het hoofdartikel over dit onderwerp.

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 $n$ groter dan 1 is de rij (voor een uitleg over de notatie $n!$ lees het artikel faculteit)

$n!+2,n!+3,\ldots ,n!+n$

een rij van $n-1$ opeenvolgende samengestelde gehele getallen, omdat

$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]$

samengesteld is voor elke $2\leq m\leq n$.

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

$(p_{i+1}-p_{i})/p_{i}$,

waarin $p_{i}$ het $i$-de priemgetal aanduidt (dat wil zeggen dat $p_{1}=2,\ p_{2}=3,$ enz.), benadert nul als $i$ naar oneindig nadert.

Open vragen

Riemann-hypothese

Zie Riemann-hypothese voor het hoofdartikel over dit onderwerp.

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 $s$ met het reële deel groter dan 1 gedefinieerd is als:

$\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ priem}}}{\frac {1}{1-p^{-s}}}$

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:

$\zeta (1)=\sum _{n=1}^{\infty }{\frac {1}{n}}=\prod _{p{\text{ priem}}}{\frac {1}{1-p^{-1}}}=\infty$

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,

$\zeta (2)=\prod _{p{\text{ priem}}}{\frac {1}{1-p^{-2}}}={\frac {\pi ^{2}}{6}}$

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 $1/\log x$ van alle getallen kleiner dan $x$ priemgetallen zijn, maar de riemann-hypothese stelt dat de asymptotische verdeling van priemgetallen ook geldig is voor veel kortere intervallen over de vierkantswortel van $x$, voor de intervallen in de buurt van $x$. 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 $n^{2}+1$ 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 $n$, er oneindig veel paren van opeenvolgende priemgetallen bestaan, die van elkaar met $2n$ 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 $n^{2}$ en $(n+1)^{2}$ bestaat voor elk positief geheel getal $n$. 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

Zie Modulair rekenen voor het hoofdartikel over dit onderwerp.

Modulair rekenen is een variant van de gebruikelijke rekenkunde. Bij het "rekenen modulo" een vast getal $n$ vinden de berekeningen plaats in de eindige verzameling ${\overline {n}}=\{1,2,\ldots ,n-1\}$ en worden resultaten steeds gereduceerd met zoveel veelvouden van $n$ dat het eindresultaat in deze verzameling ligt.

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

$3x\equiv 2{\pmod {6}}$

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

$3x\equiv 2{\pmod {7}}$

de unieke oplossing $x=3$. Op equivalent wijze is $n$ dan en slechts dan een priemgetal, als alle gehele getallen $2\leq m\leq n-1$ relatief priem zijn ten opzichte van $n$, dat wil zeggen dat hun grootste gemene deler gelijk is aan 1.

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

Groepentheorie

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

Publiekesleutelcryptografie

Zie asymmetrische cryptografie voor het hoofdartikel over dit onderwerp.

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, $x$ en $y$ met elkaar te vermenigvuldigen, met als resultaat $p$, dan om het omgekeerde te doen, en uit $p$ de waarde van $x$ en $y$ terug te rekenen, indien deze $x$ en $y$ 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.

Eigenschappen

• Als $p$ een priemgetal is en $p$ deelt een product $ab$ van natuurlijke getallen, dan is $p$ een deler van $a$ of van $b$ (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 $\mathbb {Z} /n\mathbb {Z}$ (zie modulair rekenen) is een lichaam (in België: veld) ofwel eindig lichaam dan en slechts dan als $n$ een priemgetal is. Anders gezegd: $n$ is een priemgetal dan en slechts dan als de totiëntfunctie $\varphi (n)=n-1$.
• Als $p$ een priemgetal is en $a$ is een willekeurig geheel getal, dan is $a^{p}-a$ deelbaar door $p$ (kleine stelling van Fermat).
• Als $p$ een priemgetal is anders dan 2 en 5, dan is $1/p$ altijd een repeterende breuk, met een periode van $p-1$ of een deler van $p-1$. Deze kan direct van de kleine stelling van Fermat afgeleid worden. $1/p$ uitgedrukt in een ander grondtal $q$ (dus anders dan grondtal 10) heeft het vergelijkbare effect, gegeven dat $p$ geen priemfactor is van $q$ (zie repeterende breuk voor enkele interessante eigenschappen).
• Een geheel getal $p>1$ is een priemgetal dan en slechts dan als $(p-1)!+1$ deelbaar is door $p$ (stelling van Wilson); hierbij staat het uitroepteken voor de faculteit. Omgekeerd, een geheel getal $n>4$ is samengesteld dan en slechts dan als $(n-1)!$ deelbaar is door $n$.
• Als $n$ een positief geheel getal is, dan is er altijd een priemgetal $p$ met $n<p\leq 2n$ (Postulaat van Bertrand).
• Sommering van de omgekeerden van alle priemgetallen resulteert in een divergente reeks. Meer precies, als $S(x)$ de som van de omgekeerden van alle priemgetallen $p$ is met $p\leq x$, dan $S(x)=O(\ln \ln x)$ voor $x\to \infty$ (zie Grote-O-notatie).
• Alle priemgetallen hebben de vorm $6n+1$ of $6n-1$, met als enige uitzonderingen 2 en 3, omdat de andere mogelijkheden alle deelbaar zijn door 2 of 3.
• Voor ieder priemgetal $p>2$, bestaat er een natuurlijk getal $n$ zodat $p=4n\pm 1$.
• Voor ieder priemgetal $p>3$, bestaat er een natuurlijk getal $n$ zodat $p=6n\pm 1$.
• Voor ieder priemgetal $p>3$, bestaat er een natuurlijk getal $n$ zodat $p=24n+1$.
• De karakteristiek van ieder lichaam (in België: veld) is nul of een priemgetal.
• Als $G$ een eindige groep is en $p^{n}$ is de hoogste macht van het priemgetal $p$ dat de orde van $G$ deelt, dan heeft $G$ een subgroep van orde $p^{n}$ (Stellingen van Sylow).
• Als $p$ een priemgetal is en $G$ is een groep met $p^{n}$ elementen, dan bevat $G$ een element van de orde $p$.
• De priemgetalstelling zegt dat het aantal priemgetallen kleiner dan $x$ asymptotisch $x/\ln(x)$ 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-priemgetallen?
• Is er een priemgetal tussen $n^{2}$ en $(n+1)^{2}$ voor elke $n>0$?
• Zijn er oneindig veel priemgetallen van de vorm $n^{2}+1$?
• 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) $F$. Het is ofwel $\mathbb {Q}$ of het eindige lichaam met $p$ 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 $p$ dat de eigenschap heeft dat voor willekeurige elementen $a$ en $b$ geldt dat wanneer $a\cdot b$ deelbaar is door $p$, er moet gelden dat $a$ of $b$ deelbaar is door $p$ (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 Priemideaal voor het hoofdartikel over dit onderwerp.

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

Noten

Bronnen

Externe link

• (en) Chris K. Caldwell: The PrimePages

Bijzondere getallen

Mediabestanden

Zie de categorie Prime numbers van Wikimedia Commons voor mediabestanden over dit onderwerp.