priemgetal

Een priemgetal is een natuurlijk getal groter dan 1 dat precies twee verschillende positieve delers heeft: 1 en zichzelf. Getallen met meer dan twee delers worden samengestelde getallen genoemd. Voorbeelden van priemgetallen zijn 2, 3, 5, 7, 11 en 13; 4 en 6 zijn geen priemgetallen omdat ze delers hebben naast 1 en zichzelf.

Een belangrijke eigenschap van priemgetallen is de unieke factorisatie: elk natuurlijk getal groter dan 1 kan worden uitgedrukt als een product van priemgetallen op een manier die uniek is tot de volgorde van de factoren. Dit wordt de fundamentele stelling van de getaltheorie genoemd. Er zijn onbegrensd veel priemgetallen; dit werd aangetoond door Euclides.

De verdeling van priemgetallen onder de natuurlijke getallen is wiskundig gezien grillig, maar er bestaan scherpe inzichten over hun aantallen. Zo groeit het aantal priemgetallen ≤ n ruwweg als n/log(n) (de priemgetallenstelling). Priemgetallen worden steeds moeilijker te vinden naarmate n groter wordt.

Om vast te stellen of een getal priem is, kan men eenvoudig controleren of het deelbaar is door geen enkel getal kleiner dan of gelijk aan de vierkantswortel van het getal. Voor grotere getallen bestaan efficiëntere algoritmen en probabilistische tests (bijvoorbeeld Miller-Rabin) of deterministische algoritmen voor specifieke grenzen (bijvoorbeeld AKS).

Priemgetallen spelen een centrale rol in de getaltheorie en hebben betydende toepassingen in cryptografie, zoals RSA-systemen, waar grote priemgetallen essentieel zijn voor de veiligheid van sleuteluitwisseling.