Ile jest liczb pierwszych?
Liczb pierwszych jest nieskończenie wiele.
Pierwszy nieskończoności liczb pierwszych dowiódł Euklides, który tak oto pisał:
Jest więcej liczb pierwszych, niż każda dana liczba liczb pierwszych.
Dowód Euklidesa
Przypuśćmy, że $p_1 =2 \lt p_2=3 \le \ldots \le p_r$ są wszystkimi liczbami pierwszymi. Przyjmijmy $S = p_1p_2\ldots p_r +1$ i niech $p$ będzie dzielnikiem pierwszym liczby $S$, wtedy $p$ nie może być żadną z liczb $p_1,p_2 \ldots, p_r$, bo w przeciwnym razie dzieliłaby ona różnicę $S-p_1p_2\ldots p_r=1$, co jest niemożliwe. Zatem ta liczba pierwsza $p$ jest jeszcze jedną liczbą pierwszą, co dowodzi nieskończoności liczb pierwszych.
Euklides dowodząc nieskończoności liczb pierwszych wykazał, że dla dowolnie długiej listy kolejnych liczb pierwszych, po wymnożeniu liczb z tej listy i dodaniu $1$ otrzymamy w wyniku albo liczbę pierwszą spoza listy, albo liczbę złożoną, która rozkłada się na czynniki pierwsze spoza listy. Wobec tego lista nie może być pełna, musi być więc nieskończenie długa.