Wat is een priemgetal? Uitleg en voorbeelden

Je hebt vast wel eens gehoord van priemgetallen, maar waarom zijn ze eigenlijk zo bijzonder? Van de wiskundelessen op de basisschool tot de beveiliging van je online bankieren: deze ogenschijnlijk eenvoudige getallen blijken overal om ons heen te zitten. In dit artikel ontdek je wat een priemgetal precies is, hoe je ze herkent en waarom ze onmisbaar zijn in bijvoorbeeld cryptografie.

Kleinste priemgetal: 2 · Aantal onder 1 miljoen: 78.498 · Grootste bekende (2018): 2^82.589.933 – 1 (24.862.048 cijfers) · Bewezen door Euclides: oneindig veel priemgetallen

Hieronder een overzicht van de belangrijkste feiten over priemgetallen op een rij.

Wat is een priemgetal voorbeeld?

Definitie van een priemgetal

• Een priemgetal is een natuurlijk getal groter dan 1 dat precies twee positieve delers heeft: 1 en zichzelf (Wikipedia (NL)).
• Deze definitie sluit getallen als 1 uit, omdat 1 maar één deler heeft (Boston University PDF).

Voorbeelden van priemgetallen: 2, 3, 5, 7, 11

• 2 is alleen deelbaar door 1 en 2.
• 3 is alleen deelbaar door 1 en 3.
• 5 is alleen deelbaar door 1 en 5.
• 7 is alleen deelbaar door 1 en 7.
• 11 is alleen deelbaar door 1 en 11.

Het patroon: elk van deze getallen heeft precies twee delers, wat precies de definitie van een priemgetal volgt.

Waarom 1 geen priemgetal is

Het getal 1 heeft slechts één deler (namelijk 1) in plaats van twee. Daarom voldoet het niet aan de definitie en is het geen priemgetal (Boston University PDF).

Het onderscheid tussen priemgetallen en samengestelde getallen is de basis van de getaltheorie.

Waarom is 2 een priemgetal?

Waarom 2 voldoet aan de definitie

• 2 is alleen deelbaar door 1 en 2 (Wikipedia (NL)).
• Het heeft precies twee delers, dus voldoet het aan de definitie.

Waarom 2 bijzonder is (enige even priemgetal)

• Elk even getal groter dan 2 is deelbaar door 2, dus niet alleen door 1 en zichzelf.
• Daarom is 2 het enige even priemgetal (Wikipedia (NL)).

Dat het kleinste priemgetal meteen ook een uitzondering is, maakt de getaltheorie extra interessant.

Waarom is 9 geen priemgetal?

De delers van 9: 1, 3, 9

9 heeft drie delers: 1, 3 en 9. Omdat het er meer dan twee zijn, is 9 geen priemgetal.

Verschil tussen priemgetal en samengesteld getal

• Een samengesteld getal heeft ten minste één deler naast 1 en zichzelf.
• 9 is een samengesteld getal omdat het te schrijven is als 3 × 3 (Boston University PDF).
• Voorbeeld: 9 = 3 × 3, dus het is geen priemgetal.

Het verschil tussen priem en samengesteld is essentieel voor het begrijpen van ontbinding in factoren.

Hoe weet je of iets een priemgetal is?

Methode 1: controleren op delers tot √n

1. Neem het getal n waarvan je wilt weten of het priem is.
2. Controleer of n deelbaar is door een getal tussen 2 en √n.
3. Als je geen deler vindt, is n een priemgetal.

Dit werkt omdat als n = a × b en a ≤ b, dan a ≤ √n. Je hoeft dus niet verder te zoeken dan de vierkantswortel. Deze methode wordt proefdeling genoemd.

Methode 2: gebruik van een priemgetallentabel

Je kunt een vooraf berekende lijst gebruiken, zoals de priemgetallen onder de 100: 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.

Trucje: checken of getal eindigt op 0, 2, 4, 5, 6, 8 (behalve 2 en 5)

• Als een getal (groter dan 5) eindigt op 2, 4, 6, 8 of 0, is het even en dus geen priemgetal (behalve 2).
• Als een getal eindigt op 5 (en groter is dan 5), is het deelbaar door 5 en dus geen priemgetal.

Waarom dit een snelle eerste check is: deze regel filtert de meeste samengestelde getallen eruit, maar 2 en 5 zijn uitzonderingen.

Met deze methoden kun je zelf snel bepalen of een getal priem is, zonder ingewikkelde formules.

Wat is het nut van priemgetallen?

Priemgetallen in cryptografie (RSA)

• RSA-encryptie is gebaseerd op het product van twee zeer grote priemgetallen (NIST).
• De beveiliging komt doordat het ontbinden van het product in de oorspronkelijke priemgetallen extreem moeilijk is (Georgia College & State University).
• Diffie-Hellman-sleuteluitwisseling maakt ook gebruik van priemgetallen (PubMed Central).

Priemgetallen in het dagelijks leven (pincodes, encryptie)

• Bij online betalingen en beveiligde verbindingen (HTTPS) worden priemgetallen gebruikt.
• Hashfuncties en willekeurige getallengenerators maken gebruik van priemgetallen om voorspelbaarheid tegen te gaan.
• Ook in de natuur komen priemgetallen voor: sommige cicadensoorten komen om de 13 of 17 jaar tevoorschijn – beide priemgetallen – om predatie te vermijden.

Jacht op het grootste priemgetal

Het grootste bekende priemgetal (dec. 2018) is een Mersenne-priemgetal: 2^82.589.933 – 1, met 24.862.048 cijfers. Het werd ontdekt via het GIMPS-project (Great Internet Mersenne Prime Search).

De relevantie van priemgetallen voor de moderne technologie kan nauwelijks worden overschat.

Het belang van priemgetallen reikt verder dan de wiskundeles: ze vormen de basis van de digitale beveiliging die we dagelijks gebruiken. Of je nu online betaalt, een bericht verstuurt of een wachtwoord instelt – achter de schermen zijn priemgetallen aan het werk. Voor de gemiddelde internetgebruiker in Nederland is de boodschap duidelijk: zonder priemgetallen zou privacy online een stuk lastiger zijn. Wie de basis begrijpt, snapt waarom encryptie niet zomaar ‘magie’ is, maar een elegant wiskundig principe.