Некоторые способы доказательства бесконечности простых чисел:

• Доказательство Евклида. 15 Пусть дан конечный набор простых чисел. 5 Нужно показать, что существует простое число, не входящее в этот набор. 5 Для этого перемножают числа из набора и прибавляют единицу. 15 Полученное число не делится ни на одно число из данного набора, потому что остаток от деления на любое из них даёт единицу. 15 Значит, число должно делиться на некоторое простое число, не включённое в этот набор. 15
• Доказательство с использованием факториала. 5 Факториал n! делится на любое целое от 2 до n, так как он является их произведением. 5 Следовательно, n! + 1 не делится ни на одно натуральное число от 2 до n включительно (при делении на любое из этих чисел в остатке получают 1). 5 Таким образом, n! + 1 либо само является простым, либо делится на простое число, большее n. 5 В любом случае для любого натурального числа n есть по меньшей мере одно простое число, большее n. 5 Отсюда делают вывод, что простых чисел бесконечно много. 5
• Доказательство, приведённое Эйлером. 1 Оно показывает, что сумма всех чисел, обратных к простым, расходится. 1