Πώς ο Ευκλείδης Απέδειξε ότι οι Πρώτοι Αριθμοί Είναι Άπειροι

Ο Ευκλείδης απέδειξε ότι δεν υπάρχει μέγιστος πρώτος αριθμός, δηλαδή ότι το πλήθος των πρώτων αριθμών είναι άπειρο. 

Η απόδειξή του βασίζεται στη μέθοδο της εις άτοπον απαγωγής: 

Έστω ότι υπάρχει πεπερασμένος αριθμός πρώτων αριθμών. Τότε μπορούμε να τους γράψουμε όλους σε μία λίστα: \[ 2, 3, 5, \ldots, p \] Ορίζουμε τον αριθμό: \[ N = 2 \times 3 \times 5 \times \cdots \times p + 1 \] Παρατηρούμε ότι κάθε πρώτος αριθμός της λίστας διαιρεί το γινόμενο $2 \times 3 \times \cdots \times p$, αλλά δεν διαιρεί το $N$, γιατί: \[ N \equiv 1 \pmod{q} \quad \text{για κάθε πρώτο } q \leq p \] Άρα, το $N$ είτε είναι πρώτος αριθμός, είτε έχει πρώτο διαιρέτη που δεν ανήκει στη λίστα μας. 

Και στις δύο περιπτώσεις, καταλήγουμε σε αντίφαση, αφού είχαμε υποθέσει ότι η λίστα περιέχει όλους τους πρώτους. 

Συμπέρασμα: 

Η υπόθεση είναι λανθασμένη. Επομένως, υπάρχουν άπειροι πρώτοι αριθμοί.