Priemgetallen

TERUGHome.html
Priemgetallen

Priemgetallen

Wat is een priemgetal?


Een priemgetal is een natuurlijk getal, dat slechts twee delers heeft: 1 én het getal zelf.  Elke priemgetal heeft dus twee verschillende delers: 1 én zichzelf. Natuurlijke getallen zijn alle gehele getallen boven nul; N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...}. Zo is 13 een priemgetal, want het alleen deelbaar door 1 én 13. Het getal 12 is géén priemgetal, want het is deelbaar door 1 én 12 maar ook door 2, 3, 4 en 6. Het getal 7,5 is géén priemgetal, want het is géén natuurlijk getal. De verzameling van alle priemgetallen wordt aangeduid met P.


De eerste 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, ...


In 300 v.Chr. bewees Euclides al dat er een oneindig aantal priemgetallen zijn. Van alle natuurlijke getallen is ongeveer 18% priem. Het getal 1 is per definitie géén priemgetal. De reden dat het getal 1 géén priemgetal is, heeft te maken met de eigenschappen van een positief geheel getal n: elk positief getal n is te schrijven als een reeks factoren van priemgetallen. Als n echter zelf een priemgetal is, heeft n maar één factor, één priemgetal, namelijke het getal n zelf. Als n een priemgetal is, heeft n de factoren 1 én n. Als n = 1, dan zou het getal n maar éen factor hebben en die factor is 1; terwijl een priemgetal twee factoren heeft: 1 én zichzelf. Tot de negentiende eeuw was het getal 1 nog een priemgetal. In sommige wiskunde-boeken staat nog steeds dat 1 een priemgetal is. Elk natuurlijk getal is dus te schrijven als een reeks factoren van priemgetallen. Neem het getal 240: 240 = 2 ∙ 120 = 2 ∙ 2 ∙ 60 = 2 ∙ 2 ∙ 2 ∙ 30 = 2 ∙ 2 ∙ 2 ∙ 2 ∙ 15 = 2 ∙ 2 ∙ 2 ∙ 2 ∙ 3 ∙ 5 = 24 ∙ 3 ∙ 5. Het getal 240 bestaat uit een reeks factoren van de priemgetallen 2, 3 én 5. Dat kun je bij elk getal zo doen. Het getal 43 is priem en bestaat uit de reeks van één factor 43. Priemgetallen zijn eigenlijk de bouwstenen, waaruit alle getallen bestaan.


Er is een methode om te bepalen of een getal een priemgetal is. We willen weten of het getal n priem is. Je gaat namelijk kijken of n een veelvoud van een getal m is. Het getal m ligt tussen 2 en √ n; inclusief de 2 en √ n. Ofwel: m is een geheel getal van 2 tot en met wortel n.

 Als n inderdaad een veelvoud is van een geheel getal tussen 2 én √ n is n een samengesteld getal. Een niet-priem getal is een samengesteld getal. Als n niet een veelvoud is van een geheel getal tussen 2 én √ n, is het getal n priem. Dit werkt echter alleen bij kleinere getallen. Probeer het maar eens bij: 48.387.924. Daar ben je lang mee bezig.


Zou het getal 75 een priem of een samengesteld getal zijn? We proberen bovenstaande methode: getal m ligt tussen 2 en √ 75; tussen 2 én 8,7. De gehele getallen tussen deze twee cijfers zijn: 2, 3, 4, 5, 6, 7 en 8.


Is 75 deelbaar door 2? Nee

Is 75 deelbaar door 3? Ja

Is 75 deelbaar door 4? Nee

Is 75 deelbaar door 5? Ja

Is 75 deelbaar door 6? Nee

Is 75 deelbaar door 7? Nee

Is 75 deelbaar door 8? Nee


Als één van de antwoorden positief is, is 75 samengesteld én dus niet-priem. Als alle antwoorden negatief zijn, is 75 een priemgetal. Er is geen werkende bekende formule om priemgetallen te berekenen. Er zijn al veel pogingen gedaan, inclusief door mijzelf, maar het is nog niemand gelukt. Er is echter wel iets bekend over de verdeling van priemgetallen onder alle natuurlijke getallen. Zo is bekend dat de waarschijnlijkheid van het voorkomen van priemgetallen onder een bepaald aantal getallen ongekeerd evenredig is met de grootte van het getal (de grootte is het aantal cijfers waaruit het getal bestaat). Dus hoe groter het getal, des te kleiner de waarschijnlijkheid is dat het priem is én omgekeerd. Verder is het ook zo dat ieder even natuurlijk getal een samengesteld getal is, net als ieder natuurlijk getal dat eindigt op een 5. Verder is ieder even getal (groter dan 2) gelijk aan de som van twee priemgetallen. Er is ook een oneindige aantal priem-paren; priem-paren zijn twee priemgetallen met een onderling verschil van twee.

Priemgetallen spelen een hele belangrijke rol bij de beveiliging van websites, zodat je veilig je email kunt lezen of bankzaken kunt doen. Er worden dan hele grote getallen samengesteld met priem én samengestelde priemgetallen. Om bij de bankgegevens te komen, moet je als crimineel deze getallen helemaal uitpluizen in factoren. Wiskundigen zijn als sinds de ontdekking van priemgetallen bezig om het grootste priemgetal te vinden. In 2010 staat het record op een priemgetal met 13 miljoen cijfers!


Als sinds de mens steeds meer begon te rekenen, begon de zoektocht naar de priemgetallen; gewoon voor de lol óf omdat het nut had. In het oude Egypte zijn er aanwijzingen gevonden over een systeem om priemgetallen te ontdekken, echter waren deze te onduidelijk en te vaag om mee te kunnen werken. De oudste werkende methode komt van de Griek Euclides (300 v.Chr.). Deze methode heet de zeef van Eratosthenes. Bij deze zeef zet je een helehoop getallen achter elkaar op een stuk papier of papyrus, zoals Euclides waarschijnlijk deed. Vervolgens zet je eerst een streep door alle even getallen (behalve 2, natuurlijk), zo heb je alle tweevouden weggezeefd. Vervolgens zeef je elke drievoud weg na 3. Alle viervouden zijn ook tweevouden, dus alle viervouden zijn al weggezeefd. Dan zijn de vijfvouden aan de beurt, die eindigen op 0 of 5. Alle zesvouden zijn ook drievouden en die waren al weg. Dan zeef je alle zevenvouden na 7 weg. Alle achtvouden zijn ook tweevouden, die waren al weggezeefd. Negenvouden zijn ook drievouden. Tienvouden zijn ook tweevouden, dus. Vervolgens haal je na 11 alle elfvouden weg. Twaalfvouden zijn ook tweevouden. Tenslotte zeef je na 13 alle dertienvouden weg. De getallen die overblijft zijn dan priemgetallen. Bekijk de animatie hieronder:

Bekijk hier de zeef van Eratosthenespriemgetallen_files/zeef%20animatie.swf

Na het werk van Euclides gebeurde er praktisch niets aan het werk aan priemgetallen. Pas in 1640 publiceerde Pierre de Fermat een theorie om priemgetallen te bepalen. Deze theorie werd later bewezen door Leibniz en Euler. Het schijnt dat in China deze theorie al eerder bekend was. Fermat stelde dat ieder getal van de vorm 22n + 1 priem zijn. Ze heten dan ook Fermat getallen. Fermat bewees dit tot n = 4 ( 65.537 ). Latere berekeningen lieten zien dat als n = 5, het fermatgetal 4.294.967.297 géén priemgetal is. Het is een samengsteld getal. Euler bewees later zelfs dat alle fermatgetallen met n groter dan 4 allemaal samengesteld zijn.


Marin Mersenne bekeek iets later na Pierre Fermat of getallen van de vorm: 2p -1 (met p als priemgetal) ook priem zijn en dat waren ze ook. Deze priemgetallen heten dan ook Mersenne-priemgetallen. In 1747 bewees Euler dat de even perfecte getallen gelijk zijn aan de vorm: 2p-1(2p - 1). Je ziet dat de tweede factor 2p - 1 een mersenne-priemgetal is. Gauss en Legendre kwamen onafhankelijk van elkaar er achter dat: als x naar oneindigheid neigt, het aantal priemgetallen tot x gelijk is aan x / LN(x). In 1859 zette Riemann de eerste stappen tot een algemene theorie om priemgetallen te ontdekken. Het bepalen of een getal priem is, is geen doen bij echte grote getallen. Het is onmenselijk. Daarom is een methode om dit sneller te kunnen doen erg handig. Mensen die dit ook dachten én het ook deden zijn: Pépin (1877), Proth (1878), Lehmer (1856), Lucas (1???).


Voor een lange tijd dachten wiskundigen en gewone mensen, dat priemgetallen alleen een wiskundig nut hadden. Ze zouden geen nut hebben. Tot in 1970, toen kwamen er de eerste computers. Op die computers stond geheime informatie en die moest natuurlijk beveiligd worden. Daarom werd het RSA cryptosysteem ontworpen. Zo´n RSA-systeem is gebasseerd op een zeer groot priemgetal. Deze zeer grote priemgetallen worden samen met kleinere priemgetallen samengevoegd tot één zeer heel erg groot samengesteld getal. De beveiliging hield/houdt dus in om bij de gegevens te kunnen komen dat je dat zeer heel erg groot samengesteld getal moet omzetten in een reeks van factoren van priemgetallen. De internetbeveiliging tegenwoordig is gebasseerd op dat eerste RSA-systeem uit de jaren 70, met het verschil dat er nu nog grotere priemgetallen (priemfactoren) gebruikt worden. Dat ligt aan de snelheid van de computers van nu. Er is ook een wereldwijde `strijd´ bezig tussen wiskundigen om het grootste priemgetal te ontdekken. Het is echter leuk om het grootste priemgetal te vinden, het is en blijft het grote doel om een algemene formule te vinden om priemgetal te bepalen.

Hoeveel priemgetallen zijn er?


Het aantal priemgetallen is oneindig groot. Dat bewees de Griek Euclides vóór onze jaartelling in zijn werk „Elementen: boek IX, deel 20“. Hij deed het als volgt.


Stel je een reeks voor met oneindig veel priemgetallen. Dan vermenigvuldig je al die priemgetallen en je telt er 1 bij op. Het resultaat is niet deelbaar door één van de priemgetallen uit die oneindige reeks, omdat er altijd een rest van 1 over zal blijven. Omdat alle samengestelde getallen kunnen worden ontbonden in een produkt van priemgetallen, dan zal dit resultaat (de rest!) zelf een priemgetal zijn óf er zijn één of meerdere priemgetallen waaruit de rest kan worden ontbonden. Máár één of meer van deze priemgetallen waaruit de rest bestaat, kan nooit één van de priemgetallen zijn waarmee we begonnen. De conclusie is dan: er zijn één of meer (nieuwe) priemgetallen bij gekomen. Je kunt dit proces eindeloos herhalen én er komen dus eindigeloos veel nieuwe priemgetallen bij.


In het boek „Spelen met cijfers“ uit 1959 staat het bewijs van Euclides op een simpelere manier. Geen twee opeenvolgende getallen kunnen één dezelfde factor hebben. Stel je hebt het getal x, wat deelbaar is door y. Het volgende getal x + 1 zal als het door y deelt een rest over laten van 1. Dus als we stellen dat x + 1 deelbaar zou zijn door z, dan levert x + 2 gedeeld door z een rest van 1 op.

Een ander en korter bewijs is:


dit bewijs komt zeer snel!


Hoe weet je of een getal een priemgetal is?


Er zijn verschillende manieren om te bepalen of een getal samengesteld of priem is. Zo is er de „Zeef van Eratosthenes“, die hebben we al eerder besproken. Een moderne zeef is de zeef van Sundaram en de zeef van Atkin. Hier zal ik zeer snel meer informatie over toevoegen. In het algemeen zal je een zeef niet snel gebruiken, want je wilt weten of een bepaald getal samengesteld of priem is. De meest algemene methode is zoals we al eerder besproken hebben: als je wilt weten of een getal n priem is, dan deel je n door alle gehele positieve getallen tussen 1 én de wortel van n. Als de uitkomst van één zo´n deling een geheel getal oplevert, dan is het getal n samengesteld en dus geen priemgetal. Deze methode werkt echter alleen goed bij kleinere getallen. Er zijn in de moderne methodes om te testen of een getal priem is twee richtingen waarin je kunt werken: deterministische en waarschijnlijkheids-testen. Waarschijnlijkheidstesten zijn niet voor 100% zeker: deze testen kunnen een samengesteld getal aanwijzen als een priemgetal, maar kunnen nooit een priemgetal indentificeren als een samengesteld getal. Deterministische testen hebben deze zwakte niet. De interesse in deze waarschijnlijkheidstesten, ondanks dat ze niet 100% zeker zijn, is om het feit dat ze vele malen sneller zijn dan de deterministische testen. De waarschijnlijkheidstest gaat gewoonlijk als volgt: je neemt een willekeurig getal x en controleert volgens een formule met x en de potentiele priem n. Na een aantal berekeningen wordt getal n verklaart tot „100% samengesteld“ of „waarschijnlijk priem“. Een voorbeeld met de „Fermat priem-test“; een Fermat-getal is van de volgende vorm: 22n + 1. (*) Dus als ap-1(mod p) ongelijk is aan 1, is p voor 100% samengesteld. Als xp-1(mod p) gelijk is aan 1, is p waarschijnlijk priem. Aan de andere kant, p kan samengesteld zijn als xp-1 = 1 (mod p) voor alle testgetallen x. Dat is als p een z.g.n. Carmichael getal is. In het algemeen kun je zeggen dat samengestelde getallen die „waarschijnlijk priem“ genoemd zullen worden voor alle testwaarden van x, deze getallen pseudo-priemgetallen (nep-priemgetallen) genoemd worden voor die test. Voorbeelden van testen zijn (D = deteministisch, W = waarschijnlijkheids) : AKS priem test (D), Fermat priem test (W), Lucas priem test (D), Solovay Strassen priem test (W), Miller Rabin priem test (W), Elliptic Curve priem bewijs (W), ...

Speciale priemgetallen


Er zijn speciale priemgetallen. Deze speciale getallen kun je herkennen aan de vorm van de formule waaruit ze bestaan of door het aantal cijfers in het getal. Mersenne priemgetallen zijn bijvoorbeeld te herkennen aan de formule 2p - 1 , waar p een priemgetal is. Fermat-getallen zijn weer priemgetallen van de vorm: 22n + 1. De enige bekende Fermat getallen zijn: 3, 5, 17, 257 en 65.537. Priemgetallen van de vorm: 2p + 1 (p is een priemgetal) zijn bekend als Sophie Germain priemgetallen.


Naast n! (faculteit van alle natuurlijke getallen) is er ook de uitdrukking n#. De laatste drukking is het produkt van alle priemgetallen van 2 t/m n; dus 11# is gelijk aan 2∙3∙5∙7∙11 = 2310. Zo zijn priemgetallen van de vorm p = n# ± 1 ook een speciaal geval. Ze heten priem-factor getallen. Priemgetallen van de vorm p = n! ± 1 zijn factoriale priemgetallen. Hoeveel er van de laatste twee soorten priemgetallen zijn is niet bekend.


Sinds de ontdekking van de eerste elektrische computers (ongeveer 1960) worden er steeds grotere en grotere priemgetallen gevonden. Niet alle priemgetallen hebben een mooie vorm, zoals de mersenne priemgetallen. Deze priemgetallen worden gevonden door willekeurig getallen te onderzoeken. Dat kan bijvoorbeeld zo gaan: je neemt een willekeurige waarde voor n. Je vermenigvuldigt n met 256k, waarbij k een geheel getal is. De waarde van k kies je ook zelf. Dan zoek je voor alle priemgetallen tussen 256k ∙ (n + 1) én 256k ∙ (n - 1) - 1. Op deze manier kun je nog meer priemgetallen vinden. Als je een priemgetal vindt van 100 miljoen cijfers, dan krijg je van de EFF (Electronic Frontier Foundation) een bedrag van $ 150.000 als beloning. Heeft priemgetal wat je gevonden hebt 1 miljard cijfers krijg je zelfs een beloning van $ 250.000. Het grootste gevonden priemgetal is een mersenne-priemgetal: 237.156.667 - 1. Het is 11.185.272 cijfers lang. Ik heb het geprobeerd uit te rekenen op mijn rekenmachines, maar géen één kon het aan, zo groot is het getal. Dit getal is gevonden op 23.08.2010. Er bestaat (nog?) geen formule om priemgetallen te bepalen. Degene die dat voor elkaar krijgt, zal niet worden afgescheept met slechts $ 250.000!

De verdeling van priemgetallen


Het begin om een formule te ontdekken voor priemgetallen is het zien/ontdekken van een patroon van priemgetallen tussen alle natuurlijke getallen met of zonder uitzondering(en). Van Mersenne tot een moderne algoritme op een supersnelle computer alle methode beginnen met een structuur te vinden. Niemand is het nog gelukt. Euler was goed op weg met de functie p = n2 + n + 41, maar later bleek dat die functie alleen geldt voor n < 40. Zogenaamde Heegner priemgetallen lieten een soort van structuur zien, terwijl een andere methode weer een soort spiralen lieten zien. (plaatjes staan hier onder) Methodes als de Riemann hypotese (nog steeds onbewezen), de vier Laudau´s problemen en andere proberen een patroon te ondekken in priemgetallen. Als n een natuurlijk getal is groter dan 1, dan is er altijd een priemgetal p met n < p < 2n, dus er is altijd een priemgetal p tussen n en 2n.

De zwarte puntjes zijn de priemgetallen. Je ziet duidelijk de verdeling van priemgetallen tussen de natuurlijke getallen. De ene keer zie je een patroon als hier boven en de andere keer een soort spiralen.

Een priemgat is een reeks van samengesteld getallen die tussen twee priemgetallen zitten in de reeks van natuurlijke getallen. Het priemgat tussen 13 en 17 is dus: 14, 15, 16. Deze gaten kunnen erg groot zijn.


Voor elk natuurlijk getal (n > 1), is het priemgat:


n! + 2, n! + 3, ... , n! + n


Deze reeks heeft (n - 1) samengestelde elementen, omdat:


n! + m = m ∙ (n!/m + 1) = m ∙ ((1 ∙ 2 ∙ ... ∙ (m - 1) ∙ (m + 1) ∙ ... ∙ n) + 1)


samengesteld is elke m tussen 2 én n.


Het priemgat wordt relatief kleiner als het aantal priemgetallen stijgt. De deling:


(pi + 1-pi) / pi,


waarin i het i-ste priemgetal aangeeft (p1 = 2, p2 = 3, p3 = 5, ...), nadert nul als i oneindig nadert.


Tenslotte kun je zeggen dat priemgetallen tot de verbeelding spelen. Niet alleen voor wiskundigen, maar het ook voor gewone mensen. De definitie van een priemgetal is zo simpel en toch kun je er geen vat op krijgen met een formule. Al meer dan twee eeuwen houden priemgetallen hun geheime struktuur voor zich.