Stelling van Euclides

Het is een bewijs uit het ongerijmde

Stel dat het aantal priemgetallen eindig is, dus dat alleen de getallen ${\displaystyle p_{0},p_{1},\dots ,p_{k}}$ een priemgetal zijn. Vermenigvuldig deze ${\displaystyle k}$ priemgetallen met elkaar en tel er 1 bij op, zodat het product ${\displaystyle n=p_{0}\cdot p_{1}\cdot \ldots \cdot p_{k}+1}$ ontstaat.

1. ${\displaystyle n}$ is groter dan het grootste priemgetal in de rij ${\displaystyle p_{0},p_{1},\dots ,p_{k}}$, dus is het geen priemgetal.
2. ${\displaystyle n}$ kan daarentegen door geen van de priemgetallen ${\displaystyle p_{0},p_{1},\dots ,p_{k}}$ worden gedeeld, omdat ${\displaystyle n\ {\text{mod}}\ p_{k}=1}$ voor alle ${\displaystyle k}$.

Ieder positieve, gehele getal kan volgens de hoofdstelling van de rekenkunde door tenminste een priemgetal groter dan een worden gedeeld, al is het door zichzelf. Dat betekent een tegenspraak tussen 1 en 2, dus kan de veronderstelling dat er een eindig aantal priemgetallen is niet waar zijn.