thumb|upright=1.2|De eerste 25 priemgetallen in rood.
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 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 een priemgetal is, omgekeerd evenredig is met het aantal cijfers, of de logaritme van . Deze stelling is aan het einde van de 19e eeuw bewezen. De onbewezen Riemann-hypothese, die van 1859 dateert, impliceert een verfijnde verklaring hiervan met betrekking tot de verdeling van de priemgetallen.
Ondanks intensieve studie staan veel fundamentele vragen met betrekking tot priemgetallen nog steeds open. Zo zijn bijvoorbeeld het vermoeden van Goldbach, dat beweert dat elk even getal groter dan twee de som is van twee priemgetallen, en het vermoeden van de priemtweelingen, dat zegt dat er oneindig veel priemgetaltweelingen (paren van priemgetallen, waarvan het verschil gelijk is aan twee) moeten bestaan, al meer dan een eeuw onopgelost, ondanks de ogenschijnlijke eenvoud van deze uitspraken.
Priemgetallen worden toegepast in verschillende delen van de informatietechnologie, onder andere bij het beveiligen van digitale informatie, door middel van cryptografie. Met behulp van de priemgetaltest wordt bepaald dat een getal een priemgetal is. In de asymmetrische cryptografie wordt bijvoorbeeld gebruikgemaakt van de moeilijkheid om grote getallen in hun priemfactoren te ontbinden. De zoektocht naar extreem grote priemgetallen, vaak met behulp van distributed computing, heeft de studie van de priemgetallen gestimuleerd. Begin 2013 bestond het grootst bekende priemgetal uit 17 425 170 cijfers.Website Great Internet Mersenne Prime Search In 2018 werd het tot nu toe grootste priemgetal ontdekt, dat volledig uitgeschreven uit 24 862 048 cijfers bestaat.We hebben een nieuw recordpriemgetal, De Standaard, 28 december 2018
Geschiedenis Er bevinden zich in de overgeleverde nalatenschap van het Oude Egypte hints dat men enige kennis over de priemgetallen bezat: de Egyptische breuk 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. Zij noemde deze getallen prōtos arithmòs (πρῶτος ἀριθμὸς). 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, ook gekend als de stelling van Euclides. Het bevat ook het bewijs voor 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.
Rond 1000 n. Chr. werd de stelling van Wilson voor het eerst vermeld door de Arabische wiskundige Ibn Al-Haytham, ook gekend als Alhazen. De stelling van Wilson zegt dat een natuurlijk getal een priemgetal is als en slechts als het product van alle natuurlijke getallen kleiner dan n één minder is dan een veelvoud van n. Later, in 1770, kondigde Edward Waring deze stelling aan, en werd de stelling genoemd naar zijn leerling John Wilson omdat hij deze ontdekte.
Na een lange periode gebeurde er tot de 17e eeuw niet veel met betrekking tot de studie van priemgetallen. In 1640 stelde Pierre de Fermat (overigens zonder bewijs) zijn kleine stelling van Fermat (die later werd bewezen door Leibniz en Euler). Een speciaal geval van de stelling van Fermat was mogelijk al eerder bekend aan Chinese wiskundigen. Fermat vermoedde dat alle getallen van de vorm priem zijn (ze worden naar hem fermatgetallen genoemd) en hij verifieerde dit tot en met (of ). Het volgende fermatgetal, , bleek echter een samengesteld getal te zijn (een van de priemfactoren is 641), zoals Euler later ontdekte, en waarschijnlijk zijn er evenmin grotere fermatgetallen die priem zijn. De Franse monnik Marin Mersenne bestudeerde priemgetallen van de vorm , waarin een priemgetal is. Dit type priemgetallen wordt naar hem mersennepriemgetalen genoemd.
Bij Eulers werk in de getaltheorie zaten vele resultaten met betrekking tot priemgetallen. Hij toonde aan dat de oneindige reeks divergeert. In 1747 toonde hij aan dat de even perfecte getallen exact de gehele getallen van de vorm zijn, waar de tweede priemfactor een mersennepriemgetal is.
Aan het begin van de 19e eeuw, uitten Legendre en Gauss onafhankelijk van elkaar het vermoeden, dat als naar oneindig nadert, het aantal priemgetallen tot en met asymptotisch naar nadert, waarin de natuurlijke logaritme van is. Ideeën van Riemann in zijn artikel uit 1859 over de zèta-functie schetsten de contouren van een programma, dat bijna veertig jaar later zou leiden tot een bewijs van de priemgetalstelling. Deze contouren werden in 1896 door zowel Hadamard als de la Vallée Poussin ingekleurd en afgewerkt. Beide wiskundigen vonden in hetzelfde jaar onafhankelijk van elkaar een bewijs voor de priemgetalstelling.
Voor het bewijzen dat een getal een priemgetal is, wordt (voor grote aantallen) geen gebruik van proefdelingen gemaakt. Veel wiskundigen hebben aan priemgetaltesten voor grote getallen gewerkt, waarbij zij zich vaak tot specifieke getalvormen hebben beperkt. Hiertoe behoren onder andere de Pépin-testen voor fermatgetallen (1877), de stelling van Proth (rond 1878) en de Lucas-Lehmer-priemgetaltest (dateert oorspronkelijk uit 1856),het grootst bekende priemgetal naar jaar: een korte geschiedenis Prime Curios!: 17014..05727 (39-cijfers) 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
Het cruciale belang van priemgetallen voor de getaltheorie en de wiskunde in het algemeen komt voort uit de hoofdstelling van de rekenkunde. Priemgetallen kunnen als de "bouwstenen" van de natuurlijke getallen worden beschouwd. Zo geldt bijvoorbeeld ( duidt het kwadraat van 2 aan).
Zoals in dit voorbeeld te zien is, kan hetzelfde priemgetal meer keren voorkomen. De volgorde van de priemgetallen is niet belangrijk. Herschrijven van een natuurlijk getal als het product van priemgetallen
heet het ontbinden van in priemfactoren. Ook al zijn er verschillende algoritmen om een getal in priemfactoren te ontbinden, in het bijzonder voor grotere getallen, zij zullen allemaal dezelfde priemgetallen geven.
De verzameling van alle priemgetallen wordt wel aangeduid met .
Voorbeelden en eerste eigenschappen thumb|Illustratie waaruit blijkt dat 11 een priemgetal is, terwijl 12 dat niet is
Het enige even priemgetal is 2, aangezien elk even getal, dat groter is dan twee, per definitie deelbaar door 2 is. Daarom verwijst de term oneven priemgetal naar elk priemgetal groter dan 2.
De afbeelding rechts laat op een grafische manier zien dat 12 geen priemgetal is. Priemgetallen, geschreven in het gebruikelijke decimale systeem, eindigen met uitzondering van 2 en 5, op een 1, een 3, een 7 of een 9. Dit is niet zo vreemd, omdat alle getallen die eindigen op 0, 2, 4, 6 of 8 een veelvoud van 2 en alle getallen eindigend op 0 of 5 een veelvoud van 5 zijn. Ook zijn alle priemgetallen boven de 3 van de vorm of , omdat alle andere getallen deelbaar zijn door 2 of 3. Alle priemgetallen groter dan zijn van de vorm , waarbij en geen priemfactor gemeenschappelijk heeft met of met .
Als een priemgetal is en deler is van een product van gehele getallen, dan is deler van , van of van en allebei. Dit staat bekend als het lemma van Euclides. Het wordt gebruikt om de uniciteit van de ontbinding te bewijzen, een getal kan dus 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.Gowers, 2002, pag. 118 "De schijnbaar willekeurige uitsluiting van 1 uit de definitie van een priemgetal ... drukt geen diep feit over getallen uit: maar bleek toevallig een nuttige conventie te zijn, die is overgenomen opdat er maar een manier zou zijn om een gegeven getal in priemgetallen te factoriseren.""Waarom is het getal een geen priemgetal?"
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 herdruktRiesel, 1994, p. 36. begon met 1 als het eerste priemgetal.Conway, Guy, pag. 129-130. 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".""Argumenten voor en tegen de primaliteit van het getal 1".