Priemgetal

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een priemgetal is een natuurlijk getal groter dan 1 dat slechts deelbaar is door 1 en door 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, het heeft behalve 1 en 4 ook 2 als deler. Een getal dat groter dan 1 is en geen priemgetal, heet een samengesteld getal. Priemgetallen vormen een belangrijk onderwerp in het deelgebied van de wiskunde, dat getaltheorie genoemd wordt.

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

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

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

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

Er is geen formule bekend die alle priemgetallen, maar geen samengestelde getallen oplevert. De verdeling van priemgetallen, dat wil zeggen, het statistische gedrag van grote aantallen priemgetallen, kan echter wel worden gemodelleerd. Het eerste resultaat in die richting was de priemgetalstelling, die 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.[2]

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

Priemgetallen en de hoofdstelling van de rekenkunde[bewerken]

Nuvola single chevron right.svg 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 · 2 · 3 · 13 · 149 = 22 · 3 · 13 · 149 (22 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 = p1 · p2 · ... · pt

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 vaak aangeduid met P.

Voorbeelden en eerste eigenschappen[bewerken]

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 q heeft.

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[bewerken]

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.[3][4]

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[5] begon met 1 als het eerste priemgetal.[6] 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".[7]

Ontbinden in priemfactoren[bewerken]

De hoofdstelling van de rekenkunde zegt dat elk natuurlijk getal groter dan 1 op één manier in priemfactoren is te ontbinden, dat wil zeggen kan worden geschreven als het product van priemgetallen. Er zijn verschillende algoritmen om een getal te ontbinden, zoals:

Uitprobeermethode[bewerken]

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

Voorbeelden[bewerken]

  • Bij het ontbinden 98 in priemfactoren wordt in eerste instantie gekeken naar priemgetallen kleiner of gelijk aan \sqrt{98} (dus kleiner dan 10). 98 is deelbaar door 2: 98 = 2 · 49. Vervolgens wordt gekeken naar priemgetallen kleiner of gelijk aan \sqrt{49} = 7, als deler van 49. 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 deelbaar is door 2, 3, 5 of 7, maar wel door 11, want 143 = 11 · 13. Het getal 13 is eveneens een priemgetal, dus ontbonden in priemfactoren is 143 = 11 · 13.

Het aantal priemgetallen[bewerken]

Nuvola single chevron right.svg 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. Vermenigvuldig al deze priemgetallen met elkaar en tel 1 bij dit resultaat op (zie Euclides-getal). Het resulterende getal is nu niet deelbaar door een van de priemgetallen uit de eindige verzameling, waarmee wij begonnen zijn, dit omdat delen door een van deze priemgetallen altijd een rest van 1 geeft. Omdat alle niet-priemgetallen te schrijven zijn als een product van priemgetallen, is ofwel dit resulterende getal zelf een priemgetal ofwel moet er een priemgetal zijn, waardoor het resulterende getal deelbaar is, maar dat niet zit in de oorspronkelijke eindige verzameling van priemgetallen waarmee wij begonnen zijn. Hoe dan ook, is er dus tenminste nog een priemgetal, dat geen deel uitmaakte van de eindige verzameling, waarmee wij begonnen zijn. Dit argument is van toepassing ongeacht de eindige verzameling, waarmee wij deze redenering beginnen. 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 is van al deze priemgetallen en er wordt geconcludeerd dat, omdat P + 1 niet deelbaar is door enig priemgetal, en het zelf een priemgetal is, wat een tegenspraak inhoudt (citaat G.H. Hardy[8]). 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 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59 · 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 reciproken 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 + \cdots = \infty

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

S(x) = ln ln x + O(1) voor x → ∞.

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

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, ... waar de positieve gehele getallen a en q relatief priem zijn, er oneindig veel priemgetallen zijn. De recente stelling van Green-Tao laat zien dat er willekeurig lange rijen zijn die uit priemgetallen bestaan.[12]

Verificatie van priemgetallen[bewerken]

Nuvola single chevron right.svg 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 107.[13]

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 meest eenvoudige 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 een eenvoudig algoritme, wordt het snel onpraktisch voor het testen van het "priem zijn" van grote getallen, dit omdat 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 dus te controleren met de priemgetaltest is de grootste priemfactor die wij nodig hebben, iets minder dan \scriptstyle\sqrt{n}, en zou het aantal van zulke priemfactor kandidaten dicht in de buurt liggen van \sqrt{n}/(\ln\sqrt{n} - 1). Dit aantal neemt steeds langzamer toe naar mate n groter wordt, maar omdat er belangstelling is voor grote waarden van n, is de telling ook groot: voor n = 1020 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

ap - 1 (mod p)

ongelijk is aan 1, dan is p zeker samengesteld. p kan echter ook samengesteld zijn, als ap - 1 = 1 (mod p) voor alle getuigen a, namelijk wanneer 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 meest populaire 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(log6+ε(n))
Priemtest van Fermat Nee O(k · log2n · log log n · log log log n) faalt voor Carmichael-getallen
Lucas-priemgetaltest Ja vereist factorisatie van n − 1
Solovay-Strassen-priemgetaltest 1977 Nee, foutwaarschijnlijkheid 2k O(k·log3 n)
Miller-Rabin-priemgetaltest 1980 Nee, foutwaarschijnlijkheid 4k O(k · log2 n · log log n · log log log n)
Elliptische kromme-priemgetaltest 1977 Nee O(log5+ε(n)) heuristische lopende tijd

Speciale typen van priemgetallen[bewerken]

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 2p - 1, waar 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 22n + 1 staan bekend als Fermat-priemgetallen; een regelmatige n-gon is dan en slechts dan construeerbaar met passer en liniaal als

n = 2i · m,

waar 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, waar 2p+ 1 ook een priemgetal is, staan bekend als de Sophie Germainpriemgetallen. Een priemgetal p noemt men primoriaal of priem-factoriaal, indien dit priemgetal de vorm heeft

p = n# ± 1

voor enig getal n, waar n# voor het product 2 · 3 · 5 · 7 · ... van alle priemgetallen n staat. Een priemgetal wordt factoriaal genoemd als het van de vorm n! ± 1 is. Het is niet bekend of er oneindig veel primoriale of factoriale priemgetallen zijn.

Het grootste bekende priemgetal[bewerken]

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 in 2013 grootste bekende priemgetal is 257.885.161 − 1 en bestaat uit 17.425.170 cijfers. De volgende tabel geeft de grootste bekende priemgetallen van de genoemde soorten priemgetallen:

Priemgetal Aantal decimale cijfers Soort Datum Gevonden door
257.885.161 − 1 17.425.170 mersennepriemgetal 25 januari 2013 Great Internet Mersenne Prime Search
19.249 × 213.018.586 + 1 3.918.990 niet een mersennepriemgetal (Proth-getal) 26 maart 2007 Seventeen or Bust
392.113# + 1 169.966 primoriaal priemgetal 2001 Heuer[14]
34.790! − 1 142.891 factoriaal priemgetal 2002 Marchal, Carmody en Kuosa [15]
65.516.468.355 × 233.3333 ± 1 100.355 tweeling priemgetal 2009 Tweelingpriemgetalzoektocht[16]

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 256k te vermenigvuldigen en vervolgens te zoeken naar mogelijke priemgetallen binnen het interval [256kn + 1.256k(n + 1) - 1].

De Electronic Frontier Foundation heeft in 2009 een prijs van 100.000 dollar toegekend aan GIMPS voor het als eerste ontdekken van een priemgetal dat ten minste uit 10 miljoen cijfers bestaat.[17] 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[bewerken]

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 Diophantische vergelijkingen in 9 variabelen en een parameter met de volgende eigenschap: de parameter is dan en slechts dan een priemgetal als het daaruit voortvloeiende stelsel van vergelijkingen een oplossing heeft over de natuurlijke getallen. Deze oplossing kan worden gebruikt om een enkele formule te verkrijgen met de eigenschap dat al haar positieve waarden priemgetallen zijn.

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

Geschiedenis[bewerken]

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 22n + 1 priem zijn (ze worden naar hem fermatgetallen genoemd) en hij verifieerde dit tot en met n = 4 (of 216 + 1). Het volgende fermatgetal, 232 + 1, bleek echter een samengesteld getal te zijn (een van de priemfactoren is 641), zoals Euler later ontdekte, en in feite zijn er geen fermatgetallen die priem zijn. De Franse monnik Marin Mersenne bestudeerde priemgetallen van de vorm 2p - 1, waar 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 2p - 1 (2p - 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, waar ln(x) de natuurlijke logaritme van x is. Ideeën van Riemann in zijn "artikel over de zeta-functie uit 1859" 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 gemaakt van proefdelingen. 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),[18] en de veralgemeende Lucas-priemgetaltest. Meer recente algoritmen zoals de APRT-CL, het ECPP en de AKS-test werken op willekeurige getallen, maar blijken veel langzamer dan meer specifieke priemgetaltesten.

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

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

Verdeling van de priemgetallen[bewerken]

Nuvola single chevron right.svg Zie Priemgetalstelling voor het hoofdartikel over dit onderwerp.
De 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 de dag van vandaag tevergeefs getracht om enige regelmaat in de volgorde van de priemgetallen te ontdekken, en we hebben reden om te geloven dat [de verdeling van de priemgetallen] een mysterie is, waarin de geest nooit zal doordringen.[19]

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.[20]

Euler merkte op dat de functie

n2 + 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 Ulam-spiraal toont alle natuurlijke getallen op een spiraal-achtige manier. Verrassend genoeg clusteren priemgetallen op bepaalde diagonalen, maar niet op anderen.

Het aantal priemgetallen onder een gegeven aantal[bewerken]

Nuvola single chevron right.svg Zie Priemgetal-telfunctie voor het hoofdartikel over dit onderwerp.
Een grafiek die π(n) (blauw), n/ln(n) (groen) en Li(n), de logaritmische integraalfunctie (rood) afbeeldt.

De priemgetal-telfunctie π(n) wordt gedefinieerd als het aantal priemgetallen tot en met n. Bijvoorbeeld: π(11) = 5, aangezien er vijf priemgetallen kleiner dan of gelijk aan 11 zijn. Er zijn bekende algoritmen om exacte waarden van π(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 π(1020) 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: π(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, dan bestaat er altijd een priemgetal p, waar n < p < 2n (postulaat van Bertrand).

Hiaten tussen priemgetallen[bewerken]

Nuvola single chevron right.svg 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, ..., n! + n

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

n! + m = m · (n!/m + 1) = m · [(1 · 2 · ... · (m − 1) · (m + 1) ... n) + 1]

samengesteld is voor elke 2 ≤ m ≤ 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,

waar pi het i-de priemgetal aanduidt (dat wil zeggen dat p1 = 2, p2 = 3, enz.), benadert nul als i oneindig benadert.

Open vragen[bewerken]

De Riemann-hypothese[bewerken]

Nuvola single chevron right.svg Zie Riemann-hypothese voor het hoofdartikel over dit onderwerp.

Om de Riemann-hypothese, in 2009 een van de oudste nog onbewezen wiskundige vermoedens, te kunnen formuleren is het noodzakelijk om eerst de Riemann-zeta-functie te begrijpen (s is een complex getal met reële deel groter dan 1)

\zeta(s)=\sum_{n=1}^\infin \frac{1}{n^s} = \prod_{p} \frac{1}{1-p^{-s}}.

De tweede gelijkheid is een gevolg van de hoofdstelling van de rekenkunde en laat zien dat de zeta-functie diep verbonden is met de priemgetallen. Het feit bijvoorbeeld, h(zie boven) dat er oneindig veel priemgetallen bestaan kan worden afgelezen uit de divergentie van de harmonische rijen:

\zeta(1) = \sum_{n=1}^\infin \frac{1}{n} = \prod_{p} \frac{1}{1-p^{-1}} = \infty.

Een ander voorbeeld van de rijkdom van de zeta-functie en een glimp van de moderne algebraïsche getaltheorie is de volgende identiteit (Bazel-probleem), opgesteld door Euler,

\zeta(2) = \prod_{p} \frac{1}{1-p^{-2}}= \frac{\pi^2}{6}.

De Riemann-hypothese houdt zich bezig met de nullen van de ζ-functie (dat wil zeggen, s zodanig dat ζ(s) = 0). De verbinding met priemgetallen is dat de Riemann-hypothese in essentie zegt dat de priemgetallen zo regelmatig verdeeld zijn als mogelijk is. Vanuit een natuurkundig oogpunt stelt zij ruwweg dat de onregelmatigheid in de verdeling van priemgetallen alleen afkomstig is van willekeurige ruis. Vanuit een wiskundig oogpunt, stelt zij op ruwweg dat de asymptotische verdeling van priemgetallen (ongeveer 1 / log x van alle getallen kleiner dan x zijn priemgetallen, de priemgetalstelling) ook geldig is voor veel kortere lengteintervallen over de vierkantswortel van x (voor de intervallen in de buurt van x). De Riemann- hypothese wordt algemeen verondersteld waar te zijn. Met name de eenvoudigste veronderstelling dat priemgetallen zonder goede reden geen significante onregelmatigheden mogen hebben.

Andere vermoedens[bewerken]

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 n2+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[21] en oneindig veel mersennepriemgetallen bestaan, maar men vermoedt dat het aantal Fermat-priemgetallen niet oneindig is.[22] 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 n2 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[bewerken]

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[23] 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 p[bewerken]

Nuvola single chevron right.svg Zie Modulair rekenen voor het hoofdartikel over dit onderwerp.

Modulair rekenen is een wijziging van de gebruikelijke rekenkunde, door het doen van alle berekeningen "modulo" een vast getal n. Alle berekeningen binnen de modulaire rekenkunde vinden plaats op een eindige verzameling

{0, 1, 2, ..., n - 1}.

Het berekenen van modulo n betekent dat de sommen, verschillen en producten als gewoonlijk worden berekend, maar dat na deling door n uitsluitend de rest in beschouwing wordt genomen. Laat n bijvoorbeeld zeven zijn (n = 7). Dan is in modulair rekenen modulo 7, de som 3 + 5 in plaats van 8 gelijk aan 1, dit aangezien 8 gedeeld door 7 als rest 1 heeft. Op gelijke wijze is 6 + 1 = 0 modulo 7, is 2 - 5 = 4 modulo 7 (aangezien -3 + 7 = 4) en is 3 · 4 = 5 modulo 7 (12 heeft rest 5). Standaard eigenschappen van de optelling en vermenigvuldigen die bekend zijn uit het getalsysteem van de gehele getallen of de rationale getallen blijven geldig, bijvoorbeeld

(a + b) · c = a · c + b · c (wet van de distributiviteit).

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

3 · x = 2 (modulo 6),

bijvoorbeeld een oplossing x van hetgeen een analogon van 2/3, kan niet worden opgelost, zoals men kan inzien door het berekenen van 3 · 0, ..., 3 · 5 modulo 6. Het onderscheidend kenmerk van de priemgetallen is het volgende: deling is in de modulaire rekenkunde dan en slechts dan mogelijk als n een priemgetal is. Voor n = 7 heeft de vergelijking

3 · x = 2 (modulo 7)

een unieke oplossing: x = 3. Op equivalent wijze is n dan en slechts dan een priemgetal als alle gehele getallen m die voldoen aan 2 ≤ mn - 1 relatief priem zijn ten opzichte van n, dat wil zeggen dat hun grootste gemene deler gelijk is aan 1. Door gebruik te maken van de Euler-totiënt-functie φ, is n dan en slechts dan een priemgetal als φ(n) = n - 1.

De verzameling {0, 1, 2, ..., n - 1}, met optellen en vermenigvuldigen wordt aangeduid door Z/nZ voor alle n. In het taalgebruik van de abstracte algebra, is het voor elke n een ring, maar dan en slechts dan een eindig veld als n een priemgetal is. Een aantal stellingen kunnen op een abstracte manier worden afgeleid uit de inspectie van Z/pZ. De kleine stelling van Fermat bijvoorbeeld, waarin wordt gesteld dat ap - a voor elk geheel getal a deelbaar is door p, kan met behulp van deze begrepen worden bewezen. Een gevolg hiervan is het volgende: als p een priemgetal anders dan 2 en 5 is, dan is 1/p altijd een repeterende breuk, waarvan de periode gelijk is aan p - 1 of een deler van p - 1. De fractie 1/p, eveneens uitgedrukt in basis q (in plaats van grondtal 10), heeft hetzelfde effect, 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[bewerken]

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 pn de hoogste macht van het priemgetal p is, die de orde van G deelt, dan heeft G een deelgroep van orde pn. 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[bewerken]

Nuvola single chevron right.svg 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[bewerken]

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[24] 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[25] 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.[26] 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 zeta-functie verbonden zijn met de energieniveaus van complexe kwantumsystemen.[27]

Enkele eigenschappen van priemgetallen[bewerken]

  • Als p een priemgetal is en p deelt een product ab van natuurlijke getallen, dan is p een deler van a of 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 Z/nZ (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 φ(n) = n − 1.
  • Als p een priemgetal is en a is een willekeurig geheel getal, dan is apa 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 ≤ 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 priem getallen p is met px, dan S(x) = O(ln ln x) voor x → ∞ (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 ± 1.
  • Voor ieder priemgetal p > 3, bestaat er een natuurlijk getal n zodat p = 6n ± 1.
  • Voor ieder priemgetal p > 3, bestaat er een natuurlijk getal n zodat = 24n + 1.
  • In iedere rekenkundige rij a, a + q, a + 2q, a + 3q, ... waarin de positieve gehele getallen a en q > 1 onderling ondeelbaar zijn, zijn er oneindig veel priemgetallen (Stelling van Dirichlet).
  • De karakteristiek van ieder lichaam (in België: veld) is nul of een priemgetal.
  • Als G een eindige groep is en pn is de hoogste macht van het priemgetal p dat de orde van G deelt, dan heeft G een subgroep van orde pn (Stellingen van Sylow).
  • Als p een priemgetal is en G is een groep met pn 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 over priemgetallen[bewerken]

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 n2 en (n + 1)2 voor elke n > 0?
  • Zijn er oneindig veel priemgetallen van de vorm n2 + 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[bewerken]

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, dat zowel 0 als 1 bevat. 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 knoopsom van twee triviale knopen. Elke knoop kan uniek worden uitgedrukt als een verbonden som van priemknopen.[28] Priemmodellen en priem 3-variëteiten zijn andere voorbeelden van dit type.

Ringtheorie[bewerken]

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[bewerken]

Nuvola single chevron right.svg 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.[29]

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[bewerken]

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 Nativite du Seigneur (1935) en Quatre etudes 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".[30]

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.[31]

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.[32] 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.[33]

Opmerkelijke citaten[bewerken]

"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

Trivia[bewerken]

Soms wordt priem zijn gebruikt als korte aanduiding van het begrip een priemgetal zijn. Bijvoorbeeld: "Je weet toch wel dat 91 niet priem is?"

Voetnoten[bewerken]

  1. rij A000040 in OEIS
  2. (en) Website Great Internet Mersenne Prime Search
  3. 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 im priemgetallen te factoriseren."
  4. "Waarom is het getal een geen priemgetal?"
  5. Riesel, 1994, p. 36.
  6. Conway, Guy, pag. 129-130.
  7. ""Argumenten voor en tegen de primaliteit van het getal 1".
  8. Hardy, 1908, pag. 122-123.
  9. brief in het Latijn van Goldbach aan Euler, juli 1730.
  10. Ribenboim, 2004, pag. 4.
  11. Furstenberg, 1955
  12. 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.
  13. Lehmer, 1909.
  14. De toptwintig: Primoriaal
  15. The Top Twenty: Factorial
  16. De toptwintig: Tweelingpriemgetalzoektocht
  17. Record 12-Million-Digit Prime Number Nets $100,000, Electronic Frontier Foundation
  18. het grootst bekende priemgetal naar jaar: een korte geschiedenis Prime Curios!: 17014..05727 (39-cijfers)
  19. Havil, 2003, pag. 63
  20. Havil, 2003, pag. 171
  21. Caldwell, Chris, De top twintig: Lucas-getal op de Prime Pages.
  22. zie bijvoorbeeld Guy, 1981, probleem A3, pag. 7-8.
  23. 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"
  24. Goles, E., Schulz, O. en M. Markus (2001). "Prime number selection of cycles in a predator-prey model ", Complexity 6 (4): 33-38
  25. R.A. Paulo Campos, Viviane M. de Oliveira, Ronaldo Giro, en Douglas S. Galvão. zie hier, De opkomst van priemgetallen als gevolg van de Evolutionaire Strategie, Phys. Rev Lett., vol= 93, 2004, pages 98-107
  26. The Economist, zie hier, Invasion of the Brood, 6 mei 2004
  27. Ivars Peterson, MAA Online, zie hier, De terugkeer van Zeta, 28 juni 1999
  28. Schubert, H., "Die Eindeutige Zerlegbarkeit eines Knotens in Primknoten". S.-B Heidelberger Akad. Wiss. Math.-Nat. Kl.1949 (1949), 57-104.
  29. Eisenbud, 1995, paragraaf 3.3
  30. Hill, 1995.
  31. Carl Pomerance, Priemgetallen en de speurtocht naar buitenaardse intelligentie.
  32. De muziek van priemgetallen, Marcus du Sautoys selectie van films over priemgetallen.
  33. De introductie van Paolo Giordano, Quarterly zie hier

Externe link[bewerken]