b'\n_START_ARTICLE_\nPriemgetal\n_START_PARAGRAPH_\nEen 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, 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._NEWLINE_Door de afspraak dat het getal 1 geen priemgetal is, kan onder andere de hoofdstelling van de rekenkunde eenvoudiger geformuleerd worden._NEWLINE_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._NEWLINE_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\xc3\xafllustreerd._NEWLINE_Een bepaald type priemgetallen wordt gevormd door de mersennepriemgetallen. Van een mersennegetal, dat wil zeggen een getal van de vorm , kan betrekkelijk gemakkelijk vastgesteld worden of het een priemgetal is of niet._NEWLINE_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._NEWLINE_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._NEWLINE_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\xc2\xa0425\xc2\xa0170 cijfers. In 2018 werd het tot nu toe grootste priemgetal ontdekt, dat volledig uitgeschreven uit 24\xc2\xa0862\xc2\xa0048 cijfers bestaat.\n_START_SECTION_\nVoorbeelden en eerste eigenschappen\n_START_PARAGRAPH_\nHet 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._NEWLINE_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 .  _NEWLINE_Als  een priemgetal is en  deler is van een product  van gehele getallen, dan is  deler van , van  of van  en  allebei. Dit staat bekend als het lemma van Euclides. Het wordt gebruikt om te bewijzen, dat een getal steeds maar op \xc3\xa9\xc3\xa9n manier in priemfactoren is te ontbinden._NEWLINE_De Pythagore\xc3\xabrs 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.\n_START_SECTION_\n1 wel of geen priemgetal\n_START_PARAGRAPH_\nWanneer 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._NEWLINE_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._NEWLINE_De priemgetallen hebben eigenschappen die voor 1 niet opgaan, zoals de relatie van het getal met zijn overeenkomstige waarde van de Euler-toti\xc3\xabntfunctie, of de "som-van-de-delers-functie".\n_START_SECTION_\nUitprobeermethode\n_START_PARAGRAPH_\nDe eenvoudigste manier om een getal  in priemfactoren te ontbinden is de uitprobeermethode, hoewel die manier niet erg effici\xc3\xabnt is. De methode komt erop neer de priemgetallen kleiner dan of gelijk aan , van klein naar groot te testen op deelbaarheid op . Blijkt een bepaald priemgetal  deelbaar op , dan moet  weer verder op deelbaarheid onderzocht worden, beginnend bij het priemgetal  en doorgaand tot ten hoogste .\n_START_SECTION_\nGenereren van priemgetallen\n_START_PARAGRAPH_\nEr bestaat geen bekende formule om priemgetallen te genereren die effici\xc3\xabnter is in het vinden van priemgetallen dan de hierboven genoemde methoden._NEWLINE_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._NEWLINE_Een andere formule is gebaseerd op de hierboven genoemde stelling van Wilson en genereert vele keren het getal 2 en alle andere priemgetallen precies \xc3\xa9\xc3\xa9n keer. Er bestaan soortgelijke formules die ook priemgetallen produceren.\n_START_SECTION_\nGeschiedenis\n_START_PARAGRAPH_\nEr 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._NEWLINE_Na de oude Grieken gebeurde er tot de 17e eeuw niet veel met betrekking tot de studie van priemgetallen. In 1640 stelde Pierre de Fermat (overigens zonder bewijs) zijn kleine stelling van Fermat (die later werd bewezen door Leibniz en Euler). Een speciaal geval van de stelling van Fermat was mogelijk al eerder bekend aan Chinese wiskundigen. Fermat vermoedde dat alle getallen van de vorm  priem zijn (ze worden naar hem fermatgetallen genoemd) en hij verifieerde dit tot en met  (of ). Het volgende fermatgetal, , bleek echter een samengesteld getal te zijn (een van de priemfactoren is 641), zoals Euler later ontdekte, en waarschijnlijk zijn er evenmin grotere fermatgetallen die priem zijn. De Franse monnik Marin Mersenne bestudeerde priemgetallen van de vorm , waarin  een priemgetal is. Dit type priemgetallen wordt naar hem mersennepriemgetalen genoemd._NEWLINE_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._NEWLINE_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._NEWLINE_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\xc3\xabn van Riemann in zijn artikel uit 1859 over de z\xc3\xa8ta-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\xc3\xa9e Poussin ingekleurd en afgewerkt. Beide wiskundigen vonden in hetzelfde jaar onafhankelijk van elkaar een bewijs voor de priemgetalstelling._NEWLINE_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._NEWLINE_Hiertoe behoren onder andere de P\xc3\xa9pin-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._NEWLINE_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._NEWLINE_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.\n_START_SECTION_\nAndere vermoedens\n_START_PARAGRAPH_\nNaast de Riemann-hypothese zijn er veel meer vermoedens over priemgetallen, waarvan velen al heel oud zijn: bijvoorbeeld alle vier de problemen van Landau uit 1912 (het vermoeden van Goldbach, priemtweelingen, vermoeden van Legendre en het vermoeden over  priemgetallen) zijn tot op heden nog steeds onopgelost._NEWLINE_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._NEWLINE_Een aantal vermoedens heeft betrekking op aspecten van de verdeling van priemgetallen. Men vermoedt dat er oneindig veel priemtweelingen, paren van priemgetallen met verschil 2, (priemtweelingvermoeden) bestaan. Het vermoeden van Polignac is een aanscherping van dat vermoeden, in die zin dat dit vermoeden uitspreekt dat voor elk positief geheel getal , er oneindig veel paren van opeenvolgende priemgetallen bestaan, die van elkaar met  afwijken. Het vermoeden van Brocard zegt dat er altijd ten minste vier priemgetallen tussen de kwadraten van opeenvolgende priemgetallen groter dan 2 zitten. Het vermoeden van Legendre stelt dat er een priemgetal tussen  en  bestaat voor elk positief geheel getal . Dit laatste vermoeden wordt ge\xc3\xafmpliceerd door het sterkere vermoeden van Cram\xc3\xa9r._NEWLINE_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.\n_START_SECTION_\nToepassingen\n_START_PARAGRAPH_\nVoor 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._NEWLINE_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.\n_START_SECTION_\nGroepentheorie\n_START_PARAGRAPH_\nVeel wiskundige deelgebieden maken intensief gebruik van priemgetallen. Een voorbeeld uit de theorie van de eindige groepen zijn de stellingen van Sylow: als  een eindige groep is en  de hoogste macht van het priemgetal  is, die de orde van  deelt, dan heeft  een deelgroep van orde . Elke groep met een priemorde is dus cyclisch (stelling van Lagrange)._NEWLINE_Als  een eindige groep is en  een priemgetal is, dat de orde van  deelt, dan bevat  een element van orde  (stelling van Cauchy).\n_START_SECTION_\nPriemgetallen in de natuur\n_START_PARAGRAPH_\nOnvermijdelijk 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._NEWLINE_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._NEWLINE_Er wordt gespeculeerd dat de nulpunten van de z\xc3\xa8ta-functie verbonden zijn met de energieniveaus van complexe kwantumsystemen.\n_START_SECTION_\nGeneralisaties\n_START_PARAGRAPH_\nHet 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\xc3\xab: veld) . Het is ofwel  of het eindige lichaam met  elementen, vandaar de naam. Vaak wordt er een tweede, extra betekenis bedoeld met het woord priem, namelijk dat elk object, op een in essentie unieke wijze, kan worden uitgesplitst in haar priemcomponenten. In de knopentheorie bijvoorbeeld is een priemknoop een knoop die niet kan worden geschreven als de verbonden som van twee triviale knopen. Elke knoop kan uniek worden uitgedrukt als een verbonden som van priemknopen.  Priemmodellen en priem 3-vari\xc3\xabteiten zijn andere voorbeelden van dit type.\n_START_SECTION_\nRingtheorie\n_START_PARAGRAPH_\nIn de ringtheorie beschouwt men als priemelement van een ring het element  dat de eigenschap heeft dat voor willekeurige elementen  en  geldt dat wanneer  deelbaar is door , er moet gelden dat  of  deelbaar is door  (of allebei). Uit deze definitie volgt dat een additieve inverse van een priemelement eveneens een priemelement is. Het is echter bewijsbaar dat in gangbare getallenverzamelingen, zoals de gehele getallen, een getal een priemgetal is dan en slechts dan als het irreducibel is.\n_START_SECTION_\nKunst en literatuur\n_START_PARAGRAPH_\nPriemgetallen hebben invloed uitgeoefend op veel kunstenaars en schrijvers. De Franse componist Olivier Messiaen gebruikte priemgetallen om zijn ametrische muziek via "natuurlijke fenomenen" te cre\xc3\xabren. 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\xc3\xabren: de priemgetallen 41, 43, 47 en 53 komen in een van zijn \xc3\xa9tudes voor. Volgens Messiaen werd deze manier van componeren "ge\xc3\xafnspireerd door de bewegingen van de natuur, de bewegingen van vrije en ongelijke duur"._NEWLINE_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._NEWLINE_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.\n_START_SECTION_\nTrivia\n_START_PARAGRAPH_\nSoms wordt priem zijn gebruikt als korte aanduiding van het begrip een priemgetal zijn. Bijvoorbeeld: "Je weet toch wel dat 91 niet priem is?"'