Wat is een priemgetal

Definitie

Een priemgetal is een natuurlijk getal* dat je kan delen door exact twee verschillende natuurlijke getallen. In de praktijk betekend dit, dat het getal alleen gedeeld kan worden door één en door zichzelf. Getallen die groter zijn dan 1, maar geen priemgetal zijn noem je samengestelde getallen.

*Een natuurlijk getal is een getal dat groter is dan nul.

Voorbeelden

Uitleg

Het getal 1 is geen priemgetal, omdat het maar één deler heeft, namelijk zichzelf.

Het getal 2 is wel een priemgetal omdat het twee delers heeft: (2/1=2 of 2/2=1) deler is 1 c.q. 2

Het getal 4 is geen priemgetal, omdat het meer als twee delers heeft: (4/1=4, 4/2=2, 4/4=1) deler is 1 c.q. 2 en 4.

Eerste 30 priemgetallen

De eerste reeks van 30 priemgetallen:

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, 101, 103, 107, 109, 113.

Grootst bekende priemgetal

Het groots bekende priemgetal dat bekend is heeft 12.978.189 decimalen: 2^432212609-1

Formule

Priemgetalstelling

Er is nog geen formule bekend die wel alle priemgetallen oplevert, maar geen samengestelde getallen. Het getal kan wel worden gemodelleerd. In het einde van de 19 eeuw is de priemgetalstelling bewezen.

Deze stelling zegt:

"De kans dat een willekeurig gekozen getal in de buurt van een groot getal n een priem getal is, is ongeveer gelijk aan 1/ln(n)."

Voorbeeld

Bijvoorbeeld: voor n = 1100 is de kans 1/7 terwijl voor n = 1.000.000 is de kans ca. 1/13.

De zeef van Eratosthenes

De zeef van Eratosthenes is een algoritme om priemgetallen te vinden. Deze methode is alleen efficiënt voor kleine priemgetallen.De procedure van Eratoshtenes is als volgt:

Maak een lijst van alle getallen van 2 tot een gekozen maximum B
Streep alle veelvouden van 2 door (dus niet het getal zelf)
Neem vervolgens het eerste niet doorgestreepte getal (3) en vanaf daar streep je elke veelvoud daarvan door,
Herhaal stap 3, enzovoort.
Alle overgebleven getallen zijn priemgetallen.

Voorbeeld

We zoeken alle priemgetallen tot het maximum 20.

	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
We strepen alle veelvouden van 2 weg. (dus 2x2=4 en 3x2 = 6, etc.)	2	3		5		7		9		11		13		15		17		19
We strepen alle veelvouden van 3 weg. (Dus 3x3 = 9 en 4x3 = 12, etc.)	2	3		5		7				11		13				17		19
4 is al weggestreept dus strepen we alle veelvouden van 5 weg. (Dus 5x5 = 25*)	2	3		5		7				11		13				17		19

* 5 x 5 = 25 > 20 dus de reeks is voltooid)

Alle priemgetallen met een maximum van 20 zijn dus: 2, 3, 5, 7, 11, 13, 17, 19.

Soorten priemgetallen

Priemgetallen kun je in verschillende vormen schrijven. De bekenste zijn:

Mersenne-priemgetal: 2^n-1

Proth-getal: p = k·2ⁿ+1

Primoriaal priemgetal: p = n +# 1

En meer...

Relatie tussen priemgetallen en de hoofstelling van de rekenkunde

In de wiskunde zegt de hoofdstelling van de rekenkunde dat elk positief geheel getal groter dan 1 kan worden geschreven als het product van priemgetallen en dat dit op exact één manier mogelijk is (afgezien van de volgorde van de priemgetallen).

Voorbeeld

Bijvoorbeeld n = 12. Natuurlijk kun je n op verschillende manieren in factoren ontbinden. bijvoorbeeld 12=3·4 of 12=1·2·6, maar 1, 4 en 6 zijn geen priemgetallen. Als je beperkt blijft tot priemgetallen blijft alleen: 12=2·2·3, 12=2·3·2 en 12=3·2·2 over: Slechts één mogelijkheid afgezien van de volgorde.

Moderne toepassingen

Tegenwoordig worden priemgetallen gebruikt in coderingen en voor militaire doeleinden. Een voorbeeld hiervan is RSA.

In RSA gaat het om uitwisselen van berichten in de vorm van reeksen bits. Met andere woorden:

Iemand wil jou een natuurlijk getal m sturen dat niemand anders mag zien.
Jij maakt daartoe twee getallen openbaar, namelijk n en e.
De zender stuurt aan jou r = m^emod n
Jij kunt nu wel m uit r herleiden, maar anderen kunnen dat niet.

De reden hiervoor is dat je n op een speciale manier gekozen houdt en informatie achterhoud die zelfs de zender van het bericht niet nodig heeft. Het getal n is namelijk gekozen als product van twee grote priemgetallen namelijk p en q. Deze getallen zijn zo groot dat je ervan uit mag gaan dat niemand in staat is de factoren p en q uit n te vinden.

Daarnaast heb je bij het getal e een getal d gemaakt zodanig dat (m^e)^d = m mod n voor elke keus van m. Zo’n d bestaat altijd en je kunt hem vinden uit e, p en q, maar niet uit e en n alleen.

De Amerikaanse overheid achtte het exporteren van dergelijke algoritmen in de jaren 1980 - 1990 even verderfelijk als illegale wapenexport.