Priemgetallen

Priemgetallen Voorwoord Het stond vast, ons onderwerp werd priemgetallen. Onze kennis in verband met priemgetallen reikte niet verder dan de getallen die deelbaar zijn door 1 en zichzelf. En we vroegen ons af wat er nog meer over te zeggen valt. Na even te surfen op het internet bleek al snel dat er veel informatie te vinden was. Priemgetallen hebben vele wiskundigen door de geschiedenis geboeid. Zo heb je Euclides, Fermat, Mersenne, Euler. Dit waren stuk voor stuk grote wiskundigen die geboeid waren door priemgetallen en er velen jaren over nagedacht hebben. Het grote voordeel aan een onderzoekscompetentie (OZC) met twee maken, is dat je elk maar de helft moet doen. Maar met als nadeel dat je verschillende afspraken moet maken, het werk eerlijk moet verdelen en samenkomen om alles te overlopen en tot in de details uit te werken. Onze OZC is in vier hoofdstukken ingedeeld. Eerst hebben we het over de geschiedenis van de priemgetallen en over de wiskundigen die er mee bezig waren. Hoe men steeds nieuwe priem getallen blijft vinden zien we in hoofdstuk 2. Hoofdstuk 3 gaat over de eigenschappen van de priemgetallen. Zo hebben we eerst het vermoeden van Goldbach, de belangrijkste stelling bij de priemgetallen. Daarna gaan we het hebben over de soorten priemgetallen en priemgetallen met speciale eigenschappen. Tenslotte gaat hoofdstuk 4 over de toepassingen van priemgetallen, en dit blijkt vrij veel te zijn. We hopen dat het voor u een even interessante en leerrijke ontdekkingsreis door de priemgetallen zal worden als dat het voor ons was. Hoofdstuk 1 De geschiedenis van de priemgetallen Wanneer precies de priemgetallen ontstaan zijn, kan nooit met zekerheid gezegd worden. Het zou kunnen dat de Babylonià «rs de eerste ontdekkers waren. Wel staat vast dat rond 400 voor Christus, Pythagoras de priemgetallen had gedefinieerd als getallen alleen deelbaar door 1 en zichzelf. Daarmee staat hij bekend als de uitvinder van de priemgetallen. In 530 v.C. stichte hij in het zuiden van Italià « een gemeenschap die zich onder andere bezighield met wiskunde. Er was een grote interesse in natuurlijke getallen en hun eigenschappen. Natuurlijke getallen en hun verhoudingen waren volgens de gemeenschap de basis van het leven en het heelal. Dankzij hun grote interesse, ontdekten ze iets bijzonder over bepaalde getallen. Stel een getal voor als een aantal knopen. Je kan dan sommige getallen rangschikken als een rechthoek, zoals het getal 6 (een rechthoek van 2 op 3 knopen). Er zijn getallen die je onmogelijk kan rangschikken als een rechthoek, zoals het getal 5. Er werd zo het verschil gemaakt tussen de rechtlijnige en de rechthoekige getallen. Deze rechtlijnige getallen worden nu priemgetallen genoemd. Rond 300 v.C. kwam Euclides, à ©Ãƒ ©n van de grootste wiskundigen uit de oudheid. Hij schreef een 13-delig werk De Elementen, waarin onder andere een bewijs staat dat er oneindig veel priemgetallen bestaan. Bewijs: Veronderstel dat er een grootste priemgetal pn bestaat. Dan maken we een lijst van alle priemgetallen: 2, 3, 5,,pn. Definieer dan N = 2, 3, 5, , pn. N + 1 is niet deelbaar door 2 want N is dat wel. De rest is 1. N + 1 is niet deelbaar door 3 want N is dat wel. Ook hier is de rest 1. N + 1 is niet deelbaar door 5, 7,,pn. De rest is telkens 1. Als N + 1 niet deelbaar is dan moet N + 1 zelf priem zijn. Als het wel deelbaar is, dan bestaat er een priemgetal p dat N + 1 deelt maar dat niet was opgenomen in de lijst, dus moet dat priemgetal p groter zijn dan pn. Hierdoor is er dus geen grootste priemgetal en zijn de priemgetallen oneindig. In 200 v.C. werd De Zeef van Erastosthenes (zie 2.4.1) beschreven en daarna bleef het een aantal eeuwen stil rond priemgetallen. In de 16de eeuw veronderstelde Pierre Fermat dat 22n- 1 enkel priemgetallen opleverde. Indien n een priemgetal voorstelde. Marin Mersenne dacht hetzelfde over 2n 1. In 1753 toonde Goldbach aan dat geen enkele formule voldoet om alle priemgetallen te definià «ren. Vanaf de 19de eeuw werd er intensief op zoek gegaan naar grote priemgetallen en de mogelijkheden om ze toe te passen in de samenleving. Hoofdstuk 2 Het zoeken naar priemgetallen Welke getallen zijn priem? De definitie: Een priemgetal is een natuurlijk getal dat slechts 2 verschillende delers heeft. Die delers zijn 1 en het getal zelf. In het begin is het simpel. Je kan getallen à ©Ãƒ ©n voor à ©Ãƒ ©n gaan uitproberen. Zijn ze niet deelbaar door een ander getal dan 1 en zichzelf, dan is het een priemgetal. Zo 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 alle priemgetallen kleiner dan 100. Veel mensen vragen zich af waarom 1 ook niet gewoonweg een priemgetal is. Natuurlijk heeft 1 maar à ©Ãƒ ©n deler en geen twee. Dan waarom is de definitie niet gewoon een natuurlijk getal dat enkel gedeeld kan worden door 1 en zichzelf? Wel hierdoor zou de hoofdstelling van de rekenkunde (Elk natuurlijk getal valt te ontbinden in priemfactoren op juist à ©Ãƒ ©n manier) niet meer gelden. Een natuurlijk getal zou dan op oneindig veel manieren kunnen worden geschreven als een product van priemgetallen. Eà ©n voor à ©Ãƒ ©n de getallen gaan uitproberen om na te gaan of ze priem zijn is na een tijdje toch vrij vervelend. Het zou daarom wel handig zijn een patroon in een lijst van priemgetallen te herkennen. Helaas is er tot op het heden geen enkel goede formule gevonden. Euler, in de 18de eeuw, vond de formule f(x) = x ² + x + 41 en alle f(x) zijn priem. Maar het werkt enkel voor x∈(0 t/m. 39). De principià «le hoofdtheorie De principià «le hoofdtheorie houdt in dat de kans een getal x priem is, ongeveer gelijk is aan 1/ln(x), voor een x groter dan rond de 5000. Als x rond het getal 10000 ligt, dan is de kans dat het priem is ongeveer 1/9. Ligt een getal ergens bij de 1.000.000.000 dan is de kans ongeveer 1/21. Dit betekent dat de priemgetallen zeldzamer worden naarmate we kijken naar grotere getallen. Mersenne-getallen Marin Mersenne onderzocht in het begin van de 17de eeuw ook de priemgetallen en hij probeerde net zoals Fermat een formule op te stellen. Ook hij is er niet in geslaagd, maar hij heeft wel ander belangrijk werk verricht. Hij was de eerste die zich volledig toelegde op de formule Mp = 2p -1, waarin p priem is. Euler had deze formule opgesteld in De Elementen. Deze formule werkt niet altijd. Toch is al jarenlang het grootst bekende priemgetal altijd een Mersenne-priemgetal geweest. Vanaf juni 2009 zijn er 47 Mersenne-priemgetallen bekend. Het grootst bekende priemgetal is 243112609 -1. Het was het eerste bekende priemgetal met meer dan 10 miljoen cijfers! De vlugge testen De zeef van Erastosthenes De zeef van Eratosthenes is de oudste methode voor het vinden van priemgetallen. Ze is ontstaan circa 240 voor Christus. Het werkt heel simpel. Je schrijft bijvoorbeeld alle getallen op van 2 tot en met 120 Dan nemen we het eerste getal, 2, en arceren we alle veelvouden van dit getal, groter dan het getal zelf in het rood. We nemen nu het volgende, nog niet gearceerde getal, 3, en arceren alle veelvouden van 3 in het groen. De veelvouden van 4 zijn reeds gearceerd dus kunnen we deze overslaan. Daarna arceren we alle veelvouden van 5 (blauw), van 7(geel) en van 9 (groen) De resterende getallen arceren we in het paars en dit zijn de priemgetallen van 1 t/m. 120 Met deze methode kan je alle priemgetallen t/m. n achterhalen door alle veelvouden t/m. n te arceren. Dit valt ook te bewijzen: Stel dat de zeef maar van 2 t/m 100 gaat. Stel dan dat er toch een samengesteld getal x ≠¤ 100 nog niet gearceerd is. Omdat x samengesteld is, geldt x = a.b , met a ≠¤ 100 of b ≠¤ 100. (Als a en b beide groter zijn dan 100 , is a.b = x immers groter ( 100) ²=100). x Is dus een veelvoud van een getal kleiner dan 100, Al deze veelvouden hebben we gearceerd. Elk niet gearceerd getal kleiner dan 100 kan dus niet samengesteld zijn, en moet een priemgetal zijn. Het ontbinden in priemfactoren Euclides bewees eveneens in De Elementen dat elk natuurlijk getal te ontbinden valt in priemfactoren op juist à ©Ãƒ ©n manier (als we de volgorde verwaarlozen). Dit wordt ook wel de hoofdstelling van de rekenkunde genoemd. Valt een natuurlijk getal niet te ontbinden in priemfactoren, dan is het getal priem. Bijvoorbeeld met het getal 211. Je kijkt of het deelbaar is door 2,3,5,7,11 en 13. Omdat 17 > 211mag je bij 13 stoppen. Het getal 221 is niet deelbaar door deze 6 priemgetallen, dus is het zelf priem. Deze methode wordt alleen gebruikt voor getallen met maximum 25 cijfers. Fermat In de 17de eeuw stelde Pierre de Fermat dat elk getal van de vorm Fn = 22n+ 1 (met n ∈ N een priemgetal is. Echter in 1732 zei Euler dat dit onzin is. Het werkt enkel voor n = 0 t/m 4. Je hebt enkel 2 proefdelingen nodig om deze factor te vinden. Euler toonde aan dat elke deler van een Fermat-getal Fn met n > 2 de vorm 2n+2.k + 1 heeft. In het geval van F(5) is dat 128.k + 1. De getallen 129, 385 en 513 zijn niet priem dus gaan we 257 en 641 uitproberen, met succes. Waarschijnlijk zijn alleen de eerste 5 Fermat-getallen werkelijk priemgetallen. Fermats kleine stelling daarentegen is van meer nut. Het houdt in als p een priemgetal is, dan geldt voor ieder geheel getal a dat ap = a(mod p) Als het priemgetal p geen deler is van a, dan heeft ap-1/p een rest van 1. Stel dat je een bepaald getal a hebt. Als je een priemgetal p kunt vinden waarvoor ap-1/p niet als rest 1 oplevert, dan is a deelbaar door p en dus samengesteld. Bijvoorbeeld: a=4 en p=5; dan is 1024/5 = 1020 + 4. De rest is 4, dus is het getal 1024 samengesteld en niet priem. Jammer genoeg werkt de stelling niet altijd in de andere richting, maar door deze kleine stelling van Fermat kunnen we al meteen een hele hoop getallen elimineren als priemgetallen. De andere getallen kunnen daarna verder gecontroleerd worden. PRPs De hedendaagse computertests hebben hun snelheid niet alleen te danken aan de snelle hardware, maar veeleer aan de software. Men gaat eerst een aantal waarschijnlijkheidstesten uitvoeren. Ze gaan op zoek naar pseudo-priemen. De getallen die deze testen doorstaan. De simpelste test werkt met de kleine stelling van Fermat. (zie 2.4.3) Het omgekeerde van die stelling is niet altijd geldig. Als voor een gehele a en k geldt dat ak = a(mod k) dan is k niet noodzakelijk een priemgetal. Vroeger was elke k een pseudo-priemgetal. Nu is het alleen nog maar een pseudo-priemgetal als het nog meer testen doorstaat en toch geen priemgetal blijkt te zijn. Een getal k dat in een test slaagt waarin a=2 noemt met een 2-PRP (waarschijnlijk priemgetal, een vertaling van probable prime). Als de test slaagt met a=3 noemt met het een 3-PRP enzovoort. Omdat deze priemtesten veel sneller verlopen dat de exacte controles, gaat men er meerdere na elkaar uitvoeren. Men begint bij a=2, dan a=3 enzoverder. Als een getal k positief test over verschillende testen, dan is het waarschijnlijk dat het ook een priemgetal is. Bijvoorbeeld: Een 2-PRP met k=341. Het blijkt geen priemgetal te zijn want het is deelbaar door 11 en 31. Er zijn 1.091.987.405 priemgetallen kleiner dan 25.000.000.000, maar slechts 21.853 pseudo- 2-PRP priemgetallen. Dus een getal k kleiner dan 25 miljard, die in een 2-PRP-test slaagt, in 99.998% van de gevallen ook werkelijk priem is. En hoe groter k wordt, hoe groter de slaagkans wordt. SPRPs Wanneer k het getal is dat we onderzoeken of het priem is, d oneven is en s positief. Dan is in k 1 = 2s.d , k een sterk waarschijnlijk priemgetal (vertaling van strong probable prime) als aan à ©Ãƒ ©n van de volgende condities voldaan wordt op basis a. ad = 1(mod k) (ad)2r = -1(mod k) waarbij r positief is en r Ook hier zijn alle getallen k > 1 die niet in de test slagen, niet priem. En de getallen die wel slagen kunnen priem zijn. Deze waarden voor k zijn dus niet priem. Zo een SPRP-test is redelijk snel, zeker als het gecombineerd wordt met het zoeken naar de kleinste priemfactoren. Het is aangetoond dat dergelijke testen in 75% van de gevallen priemfactoren oplevert. Op zichzelf is een SPRP-test dus tamelijk zwak, maar als we enkele van deze testen combineren, maken we een krachtige test voor kleine getallen k, die priemheid aantonen. Wat wilt zeggen dat een getal zeker priem is of zeker niet. Bijvoorbeeld: Als k k priem. Als k k priem. Als k k priem. Als k k priem. Als k k priem. Als k k priem. Deze resultaten geven ons een manier om een zeer snelle priemheidstest te maken. We beginnen met het zoeken naar de kleinste priemfactoren, daarna voeren we SPRP-testen uit op basis 2, basis 3, tot wanneer een van de bovenstaande criteria is bereikt. Bijvoorbeeld, als k De klassieke testen Merkwaardig is dat de grootste priemgetallen tot nu toe gevonden, p-1 of p+1, zeer makkelijk te ontbinden zijn. Dit komt omdat dit priemgetallen zijn waarvan het gemakkelijk is om te bewijzen dat ze priem zijn. Bij deze klassieke testen kunnen we aantonen dat een getal priem is. Dit zijn dus geen waarschijnlijkheidstesten, maar bewijzen van de priemheid. Stelling 1 (Lucas-Kraitchik-Lehmer) Lucas heeft op het einde van de 19de eeuw de kleine stelling van Fermat omgevormd tot een praktische test, die later versterkt werd door Kraitchik en Lehmer. Stel n > 1. Als voor iedere priemfactor q van n-1 er een natuurlijke a bestaat zodat an-1 = 1(mod n) a(n-1)/q ≠  1(mod n) dan is n priem. Dit is zowat de basis van alle moderne priemtesten. Stelling 2 (Pocklington) Stelling 1 heeft een volledige ontbinding in priemfactoren nodig van n-1. Pocklington had daar een oplossing voor. Stel n-1 = qkr waar q priem is en r niet deelt. Als er een natuurlijk getal a bestaat zodat an-1 = 1(mod n) en de g.g.d. van(an-1q- 1,n) = 1, dan heeft iedere priemfactor q van n de vorm qkr + 1. Stel dan n-1 = FR, waarbij F > R, g.g.d. (F,R) = 1 en de ontbinding van F gekend is. Als voor iedere priemfactor q van F er een a > 1 bestaat zodat an-1=1(mod n) g.g.d. (an-1q- 1,n) = 1 dan is n priem. Er kunnen verschillende a gebruikt worden voor ieder priemgetal q. Deze formules zijn de basis van de bekendere formules, zoals die van Pepin en Proth. Pepins test Pepin heeft in 1877 een formule gevonden die Fermat-getallen (van de vorm 22n+1) op de priemheid test. Stel dat Fn het n-de Fermat-getal is met n > 1. Fn is priem als en slechts als 3(Fn-1)/2 = 1(mod Fn). Bijvoorbeeld: F2 = 222+ 1 = 17 Dan is 3(17-1)/2 = 38 =6561 = 1(mod 17) Want (6561+1)/17 = 386 Proths test Proth maakte in 1878 de formule: n =2kh +1 met 2k > h. Als er een natuurlijk getal a bestaat zodat a(n-1)/2 = -1(mod n), dan is n priem. Lucas-Lehmertest Om na te gaan of een Mersenne-getal, een priemgetal is kan je de Lucas-Lehmer test gebruiken. Als p een priemgetal (groter dan 2) is, is het Mersenne-getal 2p -1 priem, als S(p-1) deelbaar is door 2p -1, waarbij S(n+1) = S(n) ² -2 en S(1)=4. Bijvoorbeeld: Als we willen weten of M3 = 7 een priemgetal is, dan zoeken we S(2).   Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  S(2) = S(1) ²-2   Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  = 4 ²-2   Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  Ã‚  = 14 Dan controleren we of 14 deelbaar is door 2p -1 = 7. Dat klopt dus 7 is een priemgetal. De theorie voor de test heeft Lucas uitgevonden rond 1870. Hij heeft dan de test vereenvoudigd in 1930 tot wat hierboven uitgelegd staat. Voor heel grote Mersenne-getallen wordt het wel moeilijk de test uit te voeren. Zelfs moderne computers kunnen slecht overweg met zeer grote getallen. APR, APRT-CL In 1970 begon Williams samen met enkele anderen op een andere manier de priemheid te testen. Ze gingen nu niet meer de factoren van n-1 gebruiken, maar factoren van n2+1, n ²+n+1, n ²-n+1 en nm 1 waarbij soms m heel groot was, zoals 5040. Elk priemgetal q waarvoor q 1 een deler is van 5040 (welke n niet deelt) moet dan n5040 1 delen. Er is aangetoond dat er altijd een m is waarvoor geldt dat m q die nm 1 delen met q 1 een deler van m op zijn minst een product geven dat gelijk is aann. Zo goed als altijd ligt m rond de 100.000.000 voor een n die een 3000-tal cijfers bevat. GIMPS GIMPS (Great Internet Mersenne Prime Search) is een project waarbij men zoekt naar steeds grotere Mersenne-priemgetallen. Dankzij GIMPS kunnen we enorm grote getallen controleren op priemheid, doordat het werk wordt verdeeld onder een aantal deelnemers. Het project heeft tot op het heden 12 Mersenne-priemgetallen gevonden. Iedereen die een computer heeft en over internet beschikt kan deelnemen. Er is wel veel tijd voor nodig, à ©Ãƒ ©n priemheidstest kan gemakkelijk een hele maand duren. GIMPS is een efficià «nt systeem, het zoeken naar Mersenne-getallen gebeurt in verschillende stappen. Het aanmaken van een lijst met priemgetallen (want de formule die ze gebruiken is 2p-1 met p als priemgetal) Het zoeken naar de priemfactoren, wat op verschillende manieren kan gebeuren. Bij GIMPS zullen ze de exponent eerst omzetten naar het binair talstelsel. Bijvoorbeeld: 223 1 wordt getest en wordt daarbij gedeeld door 47. In het binair is 23 = 10111. Daarna passen ze de volgende werkwijze toe (het binair rekenen): De Pollard-methode om te ontbinden in priemfactoren. De P-1-methode werkt nogal simpel. In stadium 1 kiezen ze een vaste B1. Als q = 2kp + 1, dan zal het P-1-ontbinden in factoren deze factor q bepalen zolang alle factoren van k kleiner zijn dan B1. Dan wordt x = 3E.2.P berekend. Daarna controleren ze de g.g.d. van(x 1,2p -1) om te zien of er een factor is gevonden. In stadium 2 gebruiken ze een ander vast getal, B2. Hier zal de factor q gevonden worden als k exact à ©Ãƒ ©n factor heeft tussen B1 en B1 en alle andere factoren van k kleiner zijn dan B1. (Dit stadium maakt gebruik van zeer veel geheugen) GIMPS gebruikt deze methode om de grote factoren te vinden. Bijvoorbeeld 22944999 1 dat deelbaar is door 314584703073057080643101377. B1 en B2 worden gekozen door kansberekening. De Lucas-Lehmer test. (zie : 2.5.2.2) Om een getal te controleren zijn er heel veel vermenigvuldigingen nodig. Er worden zorgvuldig algoritmes geschreven die gebruikt worden om zeer snel te vermenigvuldigen. De kans dat zo een Lucas-Lehmer test succesvol een priemgetal ontdekt is ongeveer 1/80000. De zoektocht naar het grootste priemgetal Sommige mensen hebben er een hobby van gemaakt steeds op zoek te gaan naar het grootste priemgetal. De traditie is al gaande sinds 300 v.C. toen Euclides zijn werk De Elementen schreef. Hij merkte op dat de perfecte getallen (positieve getallen gelijk aan de som van zijn delers) nogal dicht lagen bij de priemgetallen van de vorm 2p -1 voor een priemgetal p. Vanaf toen begon de jacht op de Mersenne-priemgetallen. Grote getallen van deze vorm zijn al bestudeerd door grote wiskundigen zoals Fermat, Mersenne, Euler, Lucas, Leibniz enzovoort. Veel mensen willen de eer om hun naam bij het lijstje te voegen. De traditie om grote Mersenne-priemgetallen te vinden zal zeker blijven duren. En er valt heel wat meer met mee te bereiken. Er zijn programmas om priemgetallen te zoeken bij het testen van hardware. Dit wordt al gedaan sinds het ontstaan van de computer. Zo werden stukjes software van het GIMPS project (Zie 2.7) gebruikt door Intel om de processors Pentium II en Pentium Pro te testen alvorens ze verscheept werden. De software dat priemgetallen berekent, belast de processor meer dan andere programmas doen en duurt niet lang om uit te voeren. Als je een heel groot priemgetal invoert, moet de processor een miljoen berekeningen uitvoeren om na te gaan of het wel klopt. En hoe meer priemgetallen er gevonden worden, hoe meer de verdeling ervan kan worden bestudeerd en worden begrepen. Er is al veel onderzoek gedaan naar patronen in de verdeling van priemgetallen. Tevens is het allemaal niet voor niks. Er wordt een serieuze geldprijs van minstens $ 150.000 uitgereikt aan degene die als eerste het priemgetal vindt bestaande uit 100-miljoen cijfers. De eerste die er eentje kan vinden bestaande uit een miljard cijfers, krijgt zelfs een prijs van minstens $ 250.000. Het grootste priemgetal is dus heel bruikbaar en gewild. Hoofdstuk 3 Een priemwereld vol verrassingen Inleiding Zoals al gebleken is zijn er oneindig veel priemgetallen maar kunnen we deze nog onderverdelen in aparte groepen? Ja, er zijn zelfs zeer veel onderverdelingen met elk hun specifieke eigenschappen. Zo heb je de palindroompriemgetallen, Mersennepriemgetallen, Illegale priemgetallen, Maar eerst beginnen we met het uitleggen van enkele vermoedens in verband met priemgetallen. Enkele vermoedens Inleiding Er zijn vele stellingen in verband met priemgetallen. Deze gaan van zeer simpel tot echte breinbrekers. We vooral de meest bekende en de meest belangrijke stellingen voor de priemgetallen bespreken. En daarom beginnen we ook met de stelling die van het grootste belang was voor de priemgetallen, namelijk het vermoeden van Goldbach. Het vermoeden van Goldbach Goldbach was een Duitse wiskundige en is in 1690 geboren in Kà ¶ningsberg. Hij werd zelfs leraar bij de Tsaar in Moskou omdat hij een zeer belangrijke wiskundige was in zijn tijd. Deze job gaf hem dan ook de mogelijkheid veel te reizen zodat hij overal in contact kwam met andere belangrijke wiskundigen zoals Euler, Leibniz. Hij bleef in contact met deze geleerden door middel van brieven. Ook het begin van zijn vermoeden schreef hij in 1792 in naar Euler. In deze brief schreef hij dit vermoeden: Als een geheel getal n > 5 is dan kan dit getal geschreven worden als de som van 3 priemgetallen. Bij deze 3 priemgetallen kan herhaling optreden. Wat wel vreemd is aan het hele verhaal is dat Euler een brief terugschreef met daarin de stelling dat dit vermoeden geldt voor ieder getal n > 2 maar toch is het vermoeden enkel bekend als het vermoeden van Goldbach. Euler beschouwde de stelling van Goldbach als waar maar hierbij was de stelling nog niet bewezen. Zelfs nu is de stelling nog niet bewezen desondanks er als publiciteitsstunt 1 miljoen dollar aan te verdienen was. Maar dit betekent niet dat er geen belangrijke ontdekkingen zijn gedaan. In 1939 bewees Schnirelmann dat je elk even getal groter dan 2 geschreven kan worden als een som van ten meeste 300000 priemgetallen. In 1995 bewees Ramarà © dat een som van maximum 7 priemgetallen meer dan genoeg is. Het oude vermoeden van Goldbach Dit is het vermoeden dat Goldbach als eerst vermelde in zijn brief naar Euler: als een geheel getal n > 5 is dan kan dit geschreven worden als de som van drie priemgetallen. Dit vermoeden wordt ook wel het oneven vermoeden van Goldbach genoemd. Dit oneven vermoeden is eigenlijk een zwakkere vorm van het eigenlijke vermoeden. Want we kunnen bij n > 2 telkens het priemgetal toevoegen zodat we elk oneven getal n > 5 bekomen maar het oorspronkelijke vermoeden volgt niet uit het oneven vermoeden van Goldbach. Het oneven vermoeden staat al veel dichter bij het bewijs dan het oorspronkelijke want in 1937 bewees Vinogradov dat dit vermoeden geldt voor alle voldoende grote oneven getallen. Het probleem was wel dat Vinogradov niet wist hoe groot voldoende groot nu juist was. In 1956 kon men uiteindelijk op voldoende groot een getal plakken, namelijk groter dan 3315. De waarde die gelijk is aan voldoende groot is het getal n > 1043000 bewezen door Wang. De exacte waarde zal men pas kunnen vinden als men computers kan ontwikkelen die dit soort berekeningen aankunnen. Nog meer vermoedens We zullen vlug nog even enkele vermoedens vermelden: Voor ieder even getal 2n bestaan er oneindig veel priemgetalkoppels waarvoor het verschil tussen beide priemgetallen gelijk is aan 2n. Maar indien n = 1 dan hebben we te maken met een priemtweeling en bij n = 3 dan moet het verschil 6 zijn en is het priemgetalkoppel een koppel sexy priemgetallen. (zie 3.7.2) Ieder even nummer is een verschil van 2 priemgetallen. Priemgaten Opvallend bij priemgetallen is dat er geen logische volgorde zit in de opeenvolging. Hoe verder we gaan zoeken naar grote priemgetallen hoe moeilijkere deze te vinden zijn, want ze komen dan steeds minder voor. De gaten tussen twee priemgetallen worden steeds groter hoe verder je gaat. Deze gaten oftewel priemgaten zijn de ruimtes tussen 2 opeenvolgende priemgetallen. De grootte van deze gaten wordt dus bepaald door het verschil van de 2 opeenvolgende priemgetallen. Al een gehele tijd hebben wiskundigen een patroon proberen te ontdekken bij de opeenvolging van priemgetallen door de priemgaten te bestuderen. Priemgaten hebben geen beperking in grootte want als n ≠¥ 2 de minimale grootte is dan zijn de volgende gatallen allemaal samengesteld: (n + 1)! + 2, (n + 1)! + 3, (n + 1)! + 4, , (n+ 1)! + (n + 1) Vb. n = 2 dan zijn de eerste 3 getallen van het priemgat 8,9,10 Deze formule is niet alleen nuttig om het priemgat met grootte n te geven maar ook om het priemgat te geven met minimale grootte n. Hierdoor is de aanwezigheid van minimum n ontbindbare getallen verzekerd. Wat wel nog een probleem vormt is de mannier om de grootte van een priemgat te berekenen. Want men gebruikt het eerste priemgetal a en het tweede priemgetal b om de priemgaten te berekenen door priemgetal a af te trekken van priemgetal b. Het probleem is dat men oftewel bij de uitkomst 1 moet optellen of niet, want zonder 1 toe te voegen wordt het priemgetal a ook meegerekend met het priemgat. Illegale priemgetallen In 2001 ontdekte Phil Carmody dat de gezipte broncode C, wat men op computers gebruikt om DVDs te decoderen, overeenkomt met een priemgetal. Hij ging als volgt te werk: Eerst comprimeerde hij de C-Code met het computerprogramma Gzip. Het getal wat nu weergeven werd in het verkleinde bestand was priem. Er bestaan dus heel wat illegale priemgetallen. Hieronder volgt het allereerste illegale priemgetal, gevonden door Phil Carmody. Later zette Joerg Dietrich het priemgetal om zodat deze kon worden weergegeven in baseparen. Hij kwam een Dna-sequentie uit die 43016 basen telt. Hij kwam ook tot volgende vaststelling: het zinloos zou zijn om een wet te maken tegen het gebruik van het priemgetal want als men ooit het priemgetal in ons DNA mocht vinden dan zouden 6 miljard mensen de wet overtreden. Hier is een klein deeltje van de Dna-sequentie: Merkwaardige priemgetallen Congruente priemgetallen Een priemgetal dat een regelmatige figuur vormt noemt men een congruent priemgetal. Een regelmatige figuur oftewel een regelmatige n-hoek zoals een vierkant of een gelijkzijdige driehoek. Het middelste getal of centrum vormt dan het priemgetal omgeven door cijfers van binnen naar buiten toe. Als voorbeeld geven we volgende regelmatige figuren gevormd door een priemgetal. Vb. 1 met priemgetallen Palindroompriemgetallen Priemgetallen die je zowel naar voor als naar achter hetzelfde leest noemt men palindroompriemgetallen. Als voorbeeld kunnen we volgende priemgetallen gebruiken: 2, 11, 101, Maar ook gigantische priemgetallen zoals 14 ·10^6343-4199. Dit priemgetal telt 6343 cijfers en dit is gewoon heel de tijd 1 en 4 afgewisseld: 14 ·10^6343-4199 = 1414141414141414141 Zo heb je ook het grootste palindroompriemgetal van 3 cijfers namelijk 717. Er zijn ook priemgetallen die de decimale loop van p weergeven: 3, 31, 314159, Het 4de palindroompriemgetal bevat al 38 cijfers en het 5de al 500. Nog een zeer mooi palindroompriemgetal is het volgende: 923032900000000 00000000000006660000000000 00000000000000009230329 Het bestaan uit 666 en wordt omgeven door 32 nullen en 9230329 aan elke kant. En nog wat eigenschappen van dit palindroompriemgetal: 9230329 is exact het 666ste palindroompriemgetal 666.32 = 21312 wat een palindroompriemgetal is. 666.64 = 42624 wat ook een palindroompriemgetal is. De palindroompriemgetallen zijn nog verder ingedeeld zo heb je: De Titanic-palindroompriemgetallen gevonden door Samuel Yates: deze bevatten minimum 1000 cijfers. Samuel Yates zei dat dit een zeer lage grens is en later bleek waarom. Doordat men nu verder kon rekenen met machines werd de onderverdeling Gigantische palindroompriemgetallen gemaakt: dit zijn palindroompriemgetallen met ten minste 10 000 cijfers. De Megapalindroonpriemgetallen: deze bevatten ten minste 1 000 000 getallen en er waren er in 2003 slechts 4 gekend. Een pandigitaal palindroompriemgetal: bijvoorbeeld 1023456987896543201 Als we het getal in 2 verdelen in het midden en links en rechts het midden meetellen dan hebben we elk getal 1 keer. Een zeer bijzondere eigenschap van de palindroompriemgetallen is dat ze allen oneven zijn buiten 11 want moest men een palindroomgetal vinden dat even is dan is dit misschien wel palindroom maar zeker niet priem. Nog een palindroompriemgetaleigenschap is de palindroompriempiramide: Hier begin je met een priemgetal bij de volgende rij plak je aan beide kanten deze