Priemgetal controleren
Controleer of een getal een priemgetal is en vind zijn factoren. Gebruik deze gratis priemgetaltester om elk getal onmiddellijk te testen. Geen registratie nodig.
Wat is een priemgetal?
Een priemgetal is een natuurlijk getal groter dan 1 dat exact twee verschillende factoren heeft: 1 en zichzelf. 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...
Belangrijke feiten over priemgetallen:
- 2 is het enige even priemgetal. Elke andere even getal is deelbaar door 2, dus het heeft meer dan twee factoren.
- 1 is niet priem volgens moderne conventie. Uitsluiting van 1 behoudt de unieke factorisatie (Fundamentele Stelling van de Arithmetiek).
- Priemgetallen zijn oneindig. Euclid bewees dit ongeveer 300 v.Chr.: neem een eindige lijst van alle priemgetallen p₁, p₂, ..., pₙ. Dan is het getal (p₁ × p₂ × ... × pₙ) + 1 weliswaar priem of heeft een priemfactor die niet in de lijst staat — contradictie. Daarom is de lijst oneindig.
- Als getallen groter worden, worden priemgetallen minder frequent — maar ze stoppen nooit. Er zijn 25 priemgetallen onder 100, 168 onder 1.000, en 78.498 onder 1.000.000.
Een gecombineerd getal is elk positief geheel getal groter dan 1 dat niet priem is — het heeft ten minste één factor die niet 1 en zichzelf is. Het getal 12 is gecombineerd omdat 12 = 2 × 6 = 3 × 4 = 2 × 2 × 3. Elk gecombineerd getal heeft een unieke priemfactorisatie (Fundamentele Stelling van de Arithmetiek).
Hoe controleer je of een getal priem is
Er bestaan verschillende methoden voor priemtesten, variërend van eenvoudige trialdivisie tot geavanceerde probabilistische algoritmen:
Trialdivisie (basismethode): Test of elk geheel getal van 2 tot √n deelbaar is door n. Als niet, is n priem. Je hoeft alleen te controleren tot √n omdat als n = a × b met a ≤ b, dan a ≤ √n. Als geen deelgetal wordt gevonden tot √n, is er geen boven √n.
Optimale trialdivisie: Na het controleren van de deelbaarheid door 2, controleer alleen oneven getallen. Verder: controleer 2, 3, en alleen getallen van de vorm 6k±1 (want alle priemgetallen > 3 zijn van deze vorm). Dit vermindert het aantal tests met ongeveer 66% ten opzichte van de naïeve trialdivisie.
| Getal | √n (benadering) | Test deelgetallen tot | Priem? |
|---|---|---|---|
| 97 | 9,85 | 2, 3, 5, 7 | Ja (geen deelbaar) |
| 91 | 9,54 | 2, 3, 5, 7 | Nee (7 × 13 = 91) |
| 1.009 | 31,76 | Tot 31 | Ja (priem) |
| 1.001 | 31,64 | Tot 31 | Nee (7 × 11 × 13 = 1.001) |
| 7.919 | 88,99 | Tot 89 | Ja (het 1.000ste priemgetal) |
Voor grote getallen (honderden van cijfers) is trialdivisie computationally onmogelijk. Geavanceerde tests zoals de Miller-Rabin priemtest (probabilistisch, gebruikt in cryptografie) en de AKS priemtest (deterministische polynomiale tijd, 2002) worden in plaats daarvan gebruikt.
Primfaktorisatie
Elke samengestelde getal kan worden geschreven als een unieke product van priemgetallen — zijn primfaktorisatie. Dit wordt gegarandeerd door het Fundamentele Theorem van de Arithmetica. Om de primfaktorisatie te vinden, deel je herhaaldelijk door de kleinste priemfactor:
| Getal | Primfaktorisatie | Factoreningsontbinding |
|---|---|---|
| 12 | 2² × 3 | 12 → 4×3 → 2×2×3 |
| 60 | 2² × 3 × 5 | 60 → 4×15 → 2²×3×5 |
| 100 | 2² × 5² | 100 → 4×25 → 2²×5² |
| 360 | 2³ × 3² × 5 | 360 → 8×45 → 2³×3²×5 |
| 1.024 | 2¹⁰ | Alle priemfactoren zijn 2 |
| 2.310 | 2 × 3 × 5 × 7 × 11 | Product van de eerste 5 priemgetallen |
Primfaktorisatie wordt gebruikt om de grootste gemene deler (GCD) en kleinste gemene veelvoud (LCM) van getallen te vinden. GCD(12, 18) = 2² × 3? Nee — neem de minimum macht van gedeelde priemgetallen: GCD = 2¹ × 3¹ = 6. LCM neemt de maximum macht: LCM(12, 18) = 2² × 3² = 36.
Waarom priemgetallen belangrijk zijn: Toepassingen in wiskunde en technologie
Priemgetallen zijn de "atomen" van de arithmetica — het Fundamentele Theorem van de Arithmetica stelt dat elk positief geheel getal groter dan 1 is ofwel priem of kan worden uitgedrukt als een uniek product van priemgetallen. Deze uniekeheid maakt priemgetallen de irreducibele bouwstenen van alle getallen.
Modern internetbeveiliging is afhankelijk van priemgetallen. RSA-versleuteling (gebruikt voor HTTPS, e-mailversleuteling en digitale handtekeningen) genereert openbare sleutels door twee grote priemgetallen p en q te vermenigvuldigen tot n = p × q. Versleuteling- en ontsleutelingssleutels worden berekend met behulp van modulair aritmetisch met n. De beveiliging berust op het integer factorisatieprobleem: gegeven n (een 2048-bits getal met ~617 decimale cijfers), vinden p en q is computioneel onmogelijk met de huidige technologie.
Diffie-Hellman sleuteluitwisseling gebruikt grote priemmoduli voor beveiligde sleutelovereenkomsten. Als je verbinding maakt met een website via HTTPS, worden priemgetallen stilzwijgend je gegevens in real-time te beschermen.
Hash-tabellen gebruiken priemgrote arrays om collisies te minimaliseren. Als een hashfunctie sleutels naar bucket-indices mapt, gebruiken priemgetallen als bucket-indices om een betere verdeling te garanderen omdat priemgetallen geen factoren hebben die systematische collisiepatronen kunnen creëren.
Pseudorandom getalgeneratoren (PRNGs) gebruiken priemmoduli in lineaire congruente generatoren en andere algoritmen. De periode (voor herhaling) van dergelijke generatoren is vaak gelijk aan het priemmodulus minus 1.
Speciale soorten priemgetallen
Binnen de oneindige set van priemgetallen hebben bepaalde onderdelen speciale eigenschappen of betekenis:
| Type | Definitie | Forbeelden |
|---|---|---|
| Twin priemgetallen | Priemgetallen die door 2 verschillen | (3,5), (11,13), (17,19), (41,43) |
| Mersenne priemgetallen | Priemgetallen van de vorm 2ⁿ − 1 | 3, 7, 31, 127, 8.191 |
| Fermat priemgetallen | Priemgetallen van de vorm 2^(2ⁿ) + 1 | 3, 5, 17, 257, 65.537 |
| Sophie Germain priemgetallen | p en 2p+1 zijn beide priem | 2, 3, 5, 11, 23, 29 |
| Palindroom priemgetallen | Priemgetallen die dezelfde voor- en achteruit lezen | 11, 101, 131, 151, 181 |
| Veilige priemgetallen | Priemgetallen p waarbij (p−1)/2 ook priem is | 5, 7, 11, 23, 47, 59 |
Mersenne priemgetallen (2ⁿ − 1) zijn vooral belangrijk omdat ze kunnen worden getest voor primiteit met behulp van de efficiënte Lucas-Lehmer-test. Het GIMPS-project (Groot Internet Mersenne Priemzoekproject) maakt gebruik van gedecentraliseerde rekenkracht over de hele wereld om nieuwe Mersenne priemgetallen te vinden. Tot 2024 is het grootste bekende Mersenne priemgetal 2^136.279.841 − 1, met meer dan 41 miljoen decimale cijfers.
Twin priemgetallen (paren die door 2 verschillen) zijn vermoedelijk oneindig (Twin Prime Conjecture), maar dit is nog niet bewezen — een van de meest beroemde open problemen in de wiskunde. In 2013 bewees Yitang Zhang dat er oneindig veel priemparen bestaan die door maximaal 70 miljoen verschillen, wat later werd verbeterd tot 246.
Verdeling van priemgetallen
Priemgetallen worden minder frequent wanneer getallen groter worden, maar hun verdeling volgt statistische patronen die door het Prime Number Theorem worden beschreven:
Het Prime Number Theorem (geproveerd onafhankelijk door Hadamard en de la Vallée-Poussin in 1896) stelt dat het aantal priemgetallen tot N, aangeduid als π(N), ongeveer N / ln(N) is voor grote N:
| N | Actuele π(N) | Benaderde N/ln(N) | Dichtheid |
|---|---|---|---|
| 100 | 25 | 21,7 | 1 op 4 |
| 1.000 | 168 | 144,8 | 1 op 6 |
| 10.000 | 1.229 | 1.085,7 | 1 op 8 |
| 100.000 | 9.592 | 8.685,9 | 1 op 10 |
| 1.000.000 | 78.498 | 72.382,4 | 1 op 13 |
| 1.000.000.000 | 50.847.534 | 48.254.942 | 1 op 20 |
Het Riemann Hypothesis — een van de Millennium Prize Problems met een beloning van $1 miljoen — betreft de precieze verdeling van priemgetallen. Het vermoedt dat alle niet-triviale nulstellen van de Riemann zeta-functie een reëel deel hebben van 1/2. Dit is verbonden aan hoe "willekeurig" de verdeling van priemgetallen lijkt — de hypothesen voorspelt optimale regelmaat in priemgaten.
Veelgestelde vragen
Is 1 een priemgetal?
Nee. Volgens de moderne wiskundige conventie is 1 geen priemgetal noch een samengesteld getal. Uitsluiting van 1 uit de priemgetallen behoudt de uniciteit van de priemfactorisatie (Fundamenteel Theorem van de Arithmetiek) — als 1 priem zou zijn, zou elk getal oneindig veel factorisaties hebben (bijv. 6 = 2×3 = 1×2×3 = 1×1×2×3 = ...). Historisch zijn sommige wiskundigen 1 wel als priem beschouwd, maar de moderne definitie sluit het uit.
Wat is het grootste bekende priemgetal?
Als van 2024 is het grootste bekende priemgetal 2^136,279,841 − 1 (een Mersenne-priem), ontdekt in oktober 2024. Het heeft meer dan 41 miljoen cijfers. Het Great Internet Mersenne Prime Search (GIMPS)-project vindt de meeste recordprijzen met behulp van distribueerde rekenkracht van vrijwilligers over de hele wereld. Deze enorme priemgetallen hebben geen praktische toepassingen — hun zoektocht is puur wiskundig onderzoek.
Zijn er patronen in priemgetallen?
Priemgetallen lijken willekeurig, maar patronen bestaan. Alle priemgetallen > 5 eindigen op 1, 3, 7 of 9 (nooit 0, 2, 4, 5, 6 of 8). Alle priemgetallen > 3 zijn van de vorm 6k±1. Twin-priemgetallen (die door 2 verschillen, zoals 11 en 13) lijken oneindig te blijven voortbestaan (onbewezen Twin Prime Conjecture). Het Prime Number Theorem beschrijft de statistische dichtheid van priemgetallen bij N als ongeveer 1/ln(N).
Is 2 een priemgetal?
Ja, 2 is een priemgetal — en het is het enige even priemgetal. 2 heeft exact twee factoren (1 en 2), voldoet aan de definitie. Elke andere even getal is deelbaar door 2, waardoor het samengesteld is. De priemheid van 2 is een speciaal geval dat vaak apart moet worden behandeld in algoritmen en bewijzen.
Hoe wordt primiteit gebruikt in encryptie?
RSA-encryptie maakt een sleutelpaar aan door: (1) twee grote priemgetallen p en q (elk 1024+ bits) te selecteren, (2) n = p×q te berekenen, (3) de encryptie-sleutel e en de decryptie-sleutel d te berekenen met behulp van modulair aritmetisch. Iedereen kan encrypteren met n en e (openbare sleutel), maar alleen de bezitter van p en q (of d) kan ontsleutelen. De veiligheid berust op de computatiedifficultheid van n terug te berekenen in p×q.
Wat is de snelste manier om te controleren of een getal priem is?
Voor kleine getallen (tot ~10^12): geoptimaliseerde trial divisiecontrole alleen tot √n met behulp van de 6k±1-patroon. Voor middelgrote getallen: de Miller-Rabin-primality-test met een paar getuigen is waarschijnlijk maar extreem snel. Voor zeer grote getallen (cryptografische grootte, 1000+ cijfers): waarschijnlijke tests zoals Miller-Rabin met veel willekeurige getuigen of de AKS-test voor een deterministisch bewijs.
Wat is een priemgat?
Een priemgat is de afstand tussen twee opeenvolgende priemgetallen. Het kleinste priemgat is 1 (tussen 2 en 3), en alle andere opeenvolgende priemgetallen hebben gaten van ten minste 2 (want een moet oneven zijn). Gaten groeien langzaam gemiddeld: bij N is het gemiddelde gat tussen priemgetallen ongeveer ln(N). Uitzonderlijk grote priemgaten bestaan — er zijn oneindig lange reeksen van opeenvolgende samengestelde getallen (n!+2, n!+3, ..., n!+n zijn allemaal samengesteld voor elk n).
Wat zijn de priemfactoren van 100?
100 = 2 × 50 = 2 × 2 × 25 = 2 × 2 × 5 × 5 = 2² × 5². De priemfactoren van 100 zijn 2 en 5. Deze factorisatie verklaart waarom 100 evenredig deelt door 1, 2, 4, 5, 10, 20, 25, 50 en 100 — elk deelvermogen correspondeert met een combinatie van 2⁰˒¹˒² en 5⁰˒¹˒².
Wat is Goldbach's conjectuur?
Goldbach's conjectuur (1742) stelt dat elk even getal groter dan 2 kan worden uitgedrukt als de som van twee priemgetallen. Bijvoorbeeld: 4=2+2, 6=3+3, 8=3+5, 10=3+7, 100=3+97=11+89=17+83. Het is computioneel bevestigd tot 4×10^18 maar blijft onbewezen. Het is een van de oudste en meest beroemde onopgeloste problemen in de getaltheorie.
Hoeveel priemgetallen zijn er?
Er zijn oneindig veel priemgetallen — Euclid bewees dit ongeveer 300 v.Chr. De tegenspraak: als priemgetallen beperkt waren, zou hun product plus 1 priem of een priemfactor hebben die niet in de veronderstelde complete lijst voorkomt, een tegenspraak. Terwijl priemgetallen minder dicht worden bij grotere getallen, stoppen ze nooit. Er zijn precies 78,498 priemgetallen onder 1.000.000 en 5.761.455 priemgetallen onder 100.000.000.
Prima's in Getaltheorie en Onopgeloste Problemen
Prima's staan in het centrum van sommige van de mooiste en meest vasthoudende onopgeloste problemen van de wiskunde. Begrip van deze open vragen verlicht hoeveel we weten over prima's — en hoeveel er nog mysterieus is ondanks eeuwen van inspanning.
De Riemann Hypotheese (1859): De Riemann zeta-functie ζ(s) = Σ(1/nˢ) verbindt zich met de verdeling van prima's via zijn nulpunten. De hypotheese stelt dat alle niet-triviale nulpunten op de kritische lijn Re(s) = 1/2 liggen. Als waar, zou het de meest precieze mogelijke beschrijving van hoe prima's zijn verdeeld geven. Meer dan 10 biljoen nulpunten zijn berekend en alle liggen op de kritische lijn — maar er bestaat geen bewijs. Het is een Millennium Prize Problem met een $1 miljoen prijs van de Clay Mathematics Institute.
Twin Prime Conjecture: Zijn er oneindig veel paren van prima's (p, p+2) — zoals (11,13), (17,19), (41,43), (101,103)? De conjecture zegt ja, maar het blijft onbewezen. In 2013 bewees Yitang Zhang dat er oneindig veel prima-paren zijn met een kloof van maximaal 70 miljoen — een eerste ooit vastgestelde bovengrens. Het Polymath Project verlaagde vervolgens deze bovengrens tot 246, wat betekent dat we weten dat er oneindig veel prima-paren zijn met een kloof ≤ 246. De kloof van 2 blijft onbewezen.
Goldbach's Conjecture (1742): Elke even getal groter dan 2 is de som van twee prima's. Bevestigd computationally tot 4 × 10^18. Elke even getal die getest is, voldoet eraan — vaak in veel manieren (100 = 3+97 = 11+89 = 17+83 = 29+71 = 41+59 = 47+53). Maar er bestaat geen bewijs dat alle even getallen deelt.
Mersenne-prima's en perfecte getallen: Een Mersenne-prima is een getal van de vorm 2ⁿ − 1 (waarbij n zelf een prima moet zijn). De eerste paar zijn: 3, 7, 31, 127, 8191. Er zijn er slechts 52 bekend als van 2024. Mersenne-prima's zijn verbonden aan perfecte getallen: elk Mersenne-prima genereert een even perfect getal via de formule 2^(p−1) × (2^p − 1). Het getal 28 = 4 × 7 (gebruikmakend van Mersenne-prima 7) en 496 = 16 × 31 (gebruikmakend van Mersenne-prima 31) zijn perfecte getallen. Zijn er oneindig veel Mersenne-prima's? Onbekend.
De ABC Conjecture en zijn implicaties: De ABC-conjecture (gesteld in 1985) is een diepe relatie over de priemfactoren van drie getallen a + b = c. Als bewezen, zou het Fermat's Laatste Theorem en veel andere resultaten als eenvoudige consequenties impliceren. In 2012 publiceerde Shinichi Mochizuki een bewezen bewijsgeving gebruikmakend van zijn Inter-universum Teichmüller-theorie — maar het bewijs is zo revolutionair en complex dat de wiskundige gemeenschap al meer dan een decennium heeft gedebatteerd over zijn geldigheid, met sommige wiskundigen die het accepteren en anderen een gat vinden.
Prima's blijven de ultieme wiskundige mysterie: eenvoudig om te definiëren (een getal met exact twee factoren), maar hun verdeling is complex genoeg om onopgeloste problemen te ondergraven die de grootste wiskundige geesten al eeuwenlang hebben bestreden. Elke nieuwe record-prima ontdekt, elke computatiele verificatie van een conjecture tot een nieuw limiet, en elk deelbewijs verhoogt onze kennis — terwijl het ons herinnert hoeveel er nog meer te ontdekken valt.