Priemgetallen 1: Priem en perfectie

Een interessante eigenschap van getallen is hun deelbaarheid: ze kunnen door kleinere getallen worden opgedeeld tot nieuwe natuurlijke getallen, en die kleinere getallen zijn dan hun delers. De delers van 10 zijn 1, 2, 5 en 10 zelf, bijvoorbeeld. Laten we uit die rij het getal zelf weg, dan spreken we van de echte delers (in het voorbeeld zijn 1, 2 en 5 de echte delers van 10).

 2^2 + 3^2 + 5^2 + 7^2 + 11^2 + 13^2 + 17^2 = 666

Wiskundigen definiëren verschillende soorten getallen op basis van die delers. Zo noemen we een getal perfect als de som van zijn echte delers gelijk is aan het originele getal. Om een paar voorbeelden te geven: 

6 = 1 + 2 + 3

28 = 1 + 2 + 4 + 7 + 14

496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248

8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064

Wanneer de som van de echte delers van een getal uitkomt op het getal min één, spreken we van een bijna perfect getal. Een gebrekkig getal of defect getal is een natuurlijk getal waarvan de som van de echte delers kleiner is dan het getal zelf, en een overvloedig getal is kleiner dan de som van zijn echte delers. Voorbeelden van 12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84.... En ja, er zijn ook oneven overvloedige getallen. Alleen moet je in deze rij wachten tot aan 945 (en voor wie het net even narekende, de som van de echte delers van dat getal is 975. Twee getallen zijn dan weer bevriend als de som van de echte delers van het ene getal gelijk is aan het tweede getal, en omgekeerd. Daarbij is het kleinste van de twee een overvloedig getal en het grootste een gebrekkig. Een paar voorbeelden zijn de koppels (220, 284), (1184, 1210) en (2620, 2924), en dat zijn dan meteen de drie kleinste bevriende getallen. 

Een semiperfect getal is dan weer de som van een subset van zijn delers. Neem het getal 40. Dat heeft als echte delers 1, 2, 4, 5, 8, 10 en 20. Vermits 40 gelijk is aan 2+8+10+20, is het getal meteen semiperfect. Het bovengenoemde 945 is het kleinste oneven semiperfect getal. 

Alle semiperfecte getallen zijn overvloedig, maar niet alle overvloedige getallen zijn semiperfect. Deze die het niet zijn, noemen we vreemde getallen. Een voorbeeld hiervan is 70 (en we laten het aan de geïnteresseerde lezer om uit te zoeken waarom). Wie zich nog een plaatsje in de geschiedenis van de wiskunde wil verdienen, kan zich ook best op de vreemde getallen gooien. Het is namelijk nog niet duidelijk of er ook oneven vreemde getallen bestaan. 

Tot slot zijn er ook nog de onaanraakbare getallen – zeg maar, de untouchables. Die zijn nooit gelijk aan de som van de echte delers van eender welk natuurlijk getal (ook niet van zichzelf). Voorbeelden zijn de getallen 2, 52 en 216. En ja, hier bestaat wel (minstens) een voorbeeld van een oneven onaanraakbaar getal. Ook dat mag de lezer zelf uitzoeken (maar je kan het op één hand tellen). 

 

Primaten van de natuurlijke getallen 

Priemgetallen zijn wel het bekendste voorbeeld van een groep getallen die samenhoren op basis van hun delers. Priemgetallen hebben immers geen delers, behalve 1 en zichzelf. De eerste tien priemgetallen zijn 2, 3, 5, 7, 11, 13, 17, 19, 23 en 29. 

Priemgetallen kan je echter beschouwen als de basis van de rest van de getaltheorie: net als de atomen in de scheikunde alle vormen van materie opbouwen, zo bestaan alle getallen uit een product van priemgetallen: 

6 = 2 x 3

24 = 2 x 2 x 2 x 3 

256047 = 7 x 11 x 7759

308 700 = 22 x 32 x 52 x 73

Meer nog: elk geheel getal groter dan 1 kan worden geschreven als een product van priemgetallen, op één en slechts één manier. Dit verklaart meteen de naam “priem”: het zijn de primaire bouwstenen van de structuur van de wiskunde, en kennis over priemgetallen is kennis over de schoonheid van het hele bouwwerk van de realiteit. En niettegenstaande het imago dat wetenschap en technologie hebben in onze maatschappij, is het herkennen (en erkennen) van de elegantie van dat bouwwerk wel degelijk een van de belangrijkste drijfveren achter het werk van de meeste wetenschappers. Om Henri Poincaré (Frans wiskundige, te citeren: “De wetenschapper bestudeert de natuur niet omdat deze nuttig is; hij bestudeert haar omdat hij ervan geniet, en hij geniet ervan omdat zij mooi is.” Dat verklaart waarom er gretig naar deze getallen wordt gezocht. 

Al van in de verre prehistorie dachten mensen na over priemgetallen. In de musea van het Koninklijk Belgisch Instituut voor Natuurwetenschappen ligt een botfragment (een stuk kuitbeen van een baviaan) van 24 000 jaar oud, gevonden in 1960 in toenmalig Belgisch Congo door de Belgische geoloog Jean de Heinzelin de Braucourt.  Op het beentje staan er drie kolommen met telkens een aantal gegroepeerde streepjes. De linkerkolom heeft een groep van 11 streepjes, een van 13, een van 17 en een van 19 – de priemgetallen tussen 10 en 20 dus.  

 

Het Ishango-botfragment uit het KBIN in Brussel.
Bron: Ben2, Wikimedia, CC BY-SA 3.0

 

Gezien de voorliefde van de Oude Grieken voor rekenkundige en meetkundige patronen, is het niet vreemd dat zij ook een rol speelden bij de zoektocht naar een volledige lijst van priemgetallen. Eratosthenes ontwikkelde het oudst bekende algoritme om priemgetallen op te sporen. Hiervoor maakte hij een lijst van getallen, en begon een voor een alle getallen die door een ander (kleiner) priemgetal gedeeld werden, van de lijst te schrappen. 

 

Voorstelling van de Zeef van Eratosthenes: in de rij van getallen tussen 2 en 120 schrappen we eerst alle getallen die deelbaar zijn door 2 (rood), dan die door 3 (groen), door 5 (blauw), door 7 (geel)... al wat er finaal overblijft, zijn de priemgetallen.
Bron: SKopp, Wikimedia, CC BY-SA 3.0

 

De eerste systematische behandeling van getaltheoretische stellingen over priemgetallen is ook terug te voeren op een Grieks wiskundige: de bekende Euclides, de vader van de klassieke meetkunde die in alle lagere en middelbare scholen in Vlaanderen wordt aangeleerd. Euclides is de eerste die de priemgetallen beschrijft als de bouwstenen voor de getaltheorie, en werkt ook een aantal stellingen uit over het gedrag en de eigenschappen van priemgetallen. Een van de belangrijkste inzichten die we aan hem te danken hebben, is dat er een oneindig aantal priemgetallen bestaan (minder dan het aantal natuurlijke getallen, maar toch nog altijd oneindig groot). Een stelling die doorheen de eeuwen verschillende malen bewezen werd. Bovendien stelt hij dat een gegeven natuurlijk getal slechts op één enkele manier kan geschreven worden als het product van een aantal priemgetallen: 2362 is 2 x 2 x 2 x 283. Daarmee was de man zijn tijd ver vooruit, want pas in 1801 maakte Carl Friedrich Gauss van deze stelling de hoeksteen van de getaltheorie. We noemen haar daarom vandaag de dag de Hoofdstelling van de rekenkunde.  

 

Zijn priemgetallen nuttig of enkel mooi? 

Zeer zeker, en dat is tot grote treurnis van een aantal grote wiskundigen: wiskunde wordt niet geacht nuttig te zijn, en zeker de studie van de koningin van de wiskunde, de getaltheorie, zou een zuivere theoretische activiteit moeten zijn, zeggen ze, louter gericht op het ontsluieren van de schoonheid van de natuur en haar patronen. 

Toch is niets minder waar, en zowel de natuur als de technologische mens van vandaag hebben een mooi voorbeeld van het nut van priemgetallen. 

Het natuurlijke voorbeeld vinden we bij enkele cicadensoorten. Cicaden zijn insecten die samen met de bladluizen en de wantsen thuishoren in de orde van de snavelinsecten of Hemiptera. Een aantal soorten cicaden, alle uit het genus Magicicada, hebben in de loop van de evolutie een levenscyclus gekregen die 13 of 17 jaar duurt - twee priemgetallen. Bij M. septendecim, M. cassini en M. septendecula duurt ze 17 jaar, M. neotredecim, M. tredecim, M. tredecassini en M. tredecula doen er dertien jaar over om een cicade uit een eitje te laten komen, door verschillende stadia te gaan en uiteindelijk weer eitjes te leggen. 

 

De levenscyclus van een cicade bestaat uit vier fasen. De volwassen dieren leggen eitjes, waaruit nimfen voortkomen, die zich verder ontwikkelen via een serie vervellingen. Bij het geslacht Magicicada brengen die nimfen het grootste deel van hun leven onder de grond door. Ze voeden zich met het sap uit de wortels van de bomen waar ze op leven. Na 13 (of 17) jaar beginnen ze te vervellen tot volwassen dieren en komen dan boven de grond uit. Die volwassen cicaden leven slechts 4 tot 6 weken, waarin ze moeten paren en eitjes leggen.
Tekeningen afkomstig uit The Cambridge natural history (1895) - publiek domein.


 

Magicicada septendecim
Bron: Martin Hauser, Wikimedia, CC BY-SA 2.5

 

Hoe is dat zo gekomen? Evolutionair biologen zoals Stephen Jay Gould vermoeden dat dit een succesvolle manier is om roofdieren te slim af te zijn. Door de zeer afwijkende duurtijd van hun levenscyclus vermijden deze cicaden zeer frequente confrontaties met al wat op hen jaagt, en dat verhoogt hun overlevingskansen. De soorten in het geslacht Magicicada hebben dan ook geen roofdieren die specifiek op hen jagen, maar andere soorten cicaden hebben die blijkbaar wel. Blijkbaar is het, om een of andere reden, voor de roofdieren niet zo voordelig om een levenscyclus met priemgetalduur te hebben: er zijn geen roofdieren bekend alleszins die ditzelfde gedrag vertonen. Bij de schimmels is er maar één die de cicaden blijkt te volgen: de soort Massospora cicadina. De sporen van deze lagere schimmel zijn in staat om de jonge cicaden al snel te infecteren (op het moment de dieren klaar zijn om te verpoppen naar het volwassen stadium), maar kunnen evengoed 13 of 17 jaar sluimeren voordat ze actief worden. Na infectie beginnen de schimmeldraden door het achterlijf van de cicade te woekeren (terwijl deze nog leeft), wat de cicaden steriel maakt, hen gebruikt om de schimmel over te dragen op andere cicaden, en uiteindelijk doodt.  

Maar ook de mens gebruikt priemgetallen - meer nog, we gebruiken ze elke dag, telkens wanneer we een beveiligde transactie uitvoeren met onze bankkaart. Telkens als we informatie op een beveiligde, versleutelde manier willen doorgeven, gebruiken we daarvoor (meestal toch) het RSA-algoritme, vernoemd naar de drie bedenkers Ron Rivest, Adi Shamir en Leonard Adleman. Dit algoritme is gebaseerd op het gebruik van verschillende grote priemgetallen, die moeilijk met een gewone PC uit te rekenen zijn, en zonder dewelke de eigenlijke versleuteling niet kan worden gebroken. Priemgetallen beveiligen zo onze hele digitale financiële wereld. Maar wat als we eenvoudig kunnen voorspellen welke grote getallen priemgetallen zijn en welke niet - dat zou het breken van zo een code sterk vereenvoudigen. Gelukkig bestaat de noodzakelijke wiskunde daarvoor nog niet, maar dat is een verhaal voor een volgende aflevering.

 

Deze blogpost is een aanvulling op Elementair, onze podcast over wetenschap, te vinden op Spotify en op Libsyn.

Deze podcast wordt gesteund door het Fonds Ernest Solvay via de Koning Boudewijnstichting

Geplaatst door Geert op 21/02/2020 om 20:37