Oneindig veel priemgetallen

Een priemgetal is een getal met precies twee delers. Het kleinste priemgetal is 2 en de rij gaat zo verder: 3, 5, 7, 11, 13, 17, …. Dat er nooit een eind aan deze rij komt, werd al 300 jaar voor Christus bewezen door de Griek Euclides. Hoewel het niet bekend is of Euclides de eerste is geweest die dit kon bewijzen, wordt de stelling dat er oneindig veel priemgetallen bestaan aan hem toegekend. Euclides is beroemd vanwege zijn dertiendelige boek De Elementen, waarin hij een logische opbouw van de wiskunde, met name de meetkunde, geeft.

Bouwstenen

De priemgetallen worden wel beschouwd als de bouwstenen van de gehele getallen. Elk positief geheel getal is óf priem, óf het is te schrijven als een product van priemgetallen. Zo is 8 gelijk aan 2 × 2 × 2, 9 is gelijk aan 3 × 3 en 10 is gelijk aan 2 × 5. Zo’n product van priemgetallen (de priemfactoren) heet wel de priemfactorontbinding van het betreffende getal. Omdat het getal 1 per definitie geen priemgetal is, is de priemfactorontbinding van een geheel getal groter dan 1 uniek.

Een nieuw bewijs

Filip Saidak, een Slowaaks wiskundige die tegenwoordig werkzaam is op de universiteit van North Carolina in Greensboro, publiceerde in de American Mathematical Monthly van december 2006 een nieuw bewijs van de stelling dat er oneindig veel priemgetallen bestaan. Saidaks bewijs luidt als volgt.

Stel n is een geheel getal groter dan 1. De getallen n en n + 1 verschillen slechts 1 en hebben dus geen gemeenschappelijke priemfactoren. Dat betekent dat het getal N₂ = n(n + 1) ten minste twee verschillende priemfactoren heeft. Voor de getallen N₂ en N₂ + 1 geldt hetzelfde: zij verschillen slechts 1 en moeten dus ten minste twee verschillende priemfactoren hebben. Het getal N₃ = N₂( N₂ + 1) = n(n + 1)[ n(n + 1) + 1] heeft dus minimaal drie verschillende priemfactoren. Dit proces kan eindeloos worden voortgezet: het getal N_k heeft ten minste k priemfactoren. Omdat dit voor elk positief geheel getal k geldt, kan de rij priemgetallen nooit ophouden.

Een verschil met Euclides

Saidaks bewijs is erg kort en dat geldt ook voor het bewijs van Euclides. Een belangrijk verschil tussen de twee is dat het bewijsconcept van Saidak anders is dan dat van Euclides. Het bewijs van Saidak is constructief: met zijn methode worden positieve gehele getallen gecontrueerd met een willekeurig groot aantal priemfactoren. Euclides daarentegen maakt gebruik van een bewijs uit het ongerijmde: hij neemt het tegengestelde van wat bewezen moet worden aan, en leidt daaruit een tegenstrijdigheid af.

Het bewijs van Euclides

In boek IX van De Elementen bewijst Euclides bij Propositie 20 dat er oneindig veel priemgetallen zijn. In moderne ogen ietwat merkwaardig is dat bij Euclides getallen de lengtes zijn van lijnstukken. Euclides heeft het over ‘de lengte a meet de lengte b’, waar we tegenwoordig zeggen ‘getal a is een deler van getal b’. In het onderstaande kader lees je een vrije vertaling van Euclides’ stelling en bewijs.

Euclides gemoderniseerd

In modern wiskundig taalgebruik komt Euclides’ bewijs neer op het volgende. Euclides neemt aan dat het aantal priemgetallen eindig is en uit deze vooronderstelling leidt hij een tegenspraak af. Die tegenspraak betekent dat de gemaakte vooronderstelling onjuist is, en dat het aantal priemgetallen dus oneindig moet zijn. Als de lijst van priemgetallen eindig is, kunnen we ze allemaal opschrijven: p₁, p₂, …, p_k, voor zekere k. Neem nu het product van al deze priemgetallen en tel er 1 bij op: n = p₁ x p₂ x … x p_k + 1. Dit getal n is óf een priemgetal, óf het is geen priemgetal. Als n wél priem is, is de lijst p₁, p₂, …, p_k niet compleet (dat is tegenstrijdig met de gemaakte vooronderstelling), want n is uiteraard groter dan al deze priemgetallen. Als n níét priem is, moet het door ten minste twee priemgetallen deelbaar zijn. Maar n is door geen enkel van de getallen p₁, p₂, …, p_k deelbaar, want het getal n – 1 (het product van p₁, p₂, …, p_k) is reeds door al die getallen deelbaar. Twee getallen die slechts 1 verschillen, kunnen nooit gemeenschappelijke delers hebben. Dat betekent dat de priemfactoren van n niet in de lijst p₁, p₂, …, p_k voorkomen, wat in tegenspraak is met de gemaakte vooronderstelling.

Andere bewijzen

Saidak is niet de eerste die met een alternatief bewijs voor de stelling van Euclides komt. In 1878 kwam Ernst Eduard Kummer (1810-1893) met een kort en zeer elegant bewijs. Kummer maakt net als Euclides gebruik van een bewijs uit het ongerijmde.

Andere bewijzen variëren sterk in zowel de lengte als de aanpak. Er bestaat een bewijs, eveneens uit het ongerijmde, dat gebruik maakt van getallen van de vorm 2ⁿ – 1, de zogeheten Mersenne-getallen. Hierbij wordt bewezen dat áls p het grootste priemgetal zou zijn, de priemfactoren van het getal 2^p – 1 groter dan p moeten zijn, wat in tegenspraak is met de veronderstelling dat p het grootste priemgetal is.

De beroemde Leonhard Euler (1707-1783) bewees dat de reeks 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + … (in de noemers staan de priemgetallen) divergeert, dat wil zeggen: deze som kan willekeurig groot worden. Daaruit volgt dat de rij priemgetallen nooit kan ophouden, omdat dan ook de genoemde som uit slechts eindig veel termen zou bestaan.

Christian Goldbach (1690-1764) schreef in 1730 in een brief aan Euler dat hij een nieuw bewijs had gevonden voor het bestaan van oneindig veel priemgetallen. Goldbach maakt hierbij gebruik van de zogenaamde Fermat-getallen, dat zijn getallen van de vorm 2²ⁿ + 1, waarbij n een niet-negatief geheel getal is.

In 1955 kwam Harry Fürstenberg met een verrassend bewijs. Hij gebruikte de topologie, een tak van de wiskunde die je niet als vanzelfsprekend in verband brengt met de getaltheorie, om de stelling van Euclides te bewijzen.

Tussen een getal en het dubbele van dat getal ligt altijd een priemgetal; hieruit volgt eveneens dat er oneindig veel priemgetallen moeten bestaan. Dit resultaat kan ook op meerdere manieren worden bewezen. Een elegant bewijs gaf de Hongaar Paul Erdös (1913-1996), een van de invloedrijkste wiskundigen uit de twintigste eeuw. Hij bewees eveneens – en daarmee was hij de eerste – dat er altijd een priemgetal van de vorm 4m + 1 en één van de vorm 4n + 3 bestaan tussen een getal en het dubbele van dat getal. Bijvoorbeeld: tussen 100 en 200 liggen de priemgetallen 101 en 103 (m = n = 25).

Het nieuwe bewijs van Saidak kan worden toegevoegd aan de vele verschillende bewijzen die in de geschiedenis van de wiskunde zijn gevonden voor Euclides’ stelling. Het is opmerkelijk dat een verrassend simpel bewijs als dat van Saidak nog niet eerder was bedacht.