Бесконечность простых чисел

Простые числа никогда не кончаются — и это можно доказать в три строки.

Теорема Евклида — простых чисел бесконечно много.

Глядя на список простых — 2, 3, 5, 7, 11, 13, … — кажется, что они становятся всё реже. Между 1 и 10 их четыре, между 90 и 100 — лишь одно (97). Возникает естественный вопрос: а вдруг они когда-нибудь закончатся? Евклид ответил на него около 300 года до нашей эры, и его рассуждение остаётся одним из самых элегантных во всей математике.

Доказательство от противного

Предположим обратное: простых чисел конечное число, и это $p_1, p_2, \dots, p_k$ — весь список до последнего. Рассмотрим число

$$P = p_1 \cdot p_2 \cdot \ldots \cdot p_k + 1.$$

Что это за число? Оно больше любого из наших простых, поэтому в список не входит — значит, по нашему предположению, оно составное и делится на какое-то из $p_i$. Но при делении $P$ на любое $p_i$ остаётся остаток 1: ведь $p_1 \cdots p_k$ делится на $p_i$ нацело, а мы добавили единицу. Получили противоречие: $P$ не делится ни на одно простое из списка, но всякое число больше единицы обязано иметь простой делитель. Значит, список был неполным, и простых бесконечно много.

Проверим идею кодом

Возьмём несколько первых простых, перемножим, прибавим единицу и посмотрим на простой делитель результата — он всегда «новый»:

from math import prod

def smallest_prime_factor(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return d
        d += 1
    return n  # само n простое

start = [2, 3, 5, 7, 11, 13]
for k in range(1, len(start) + 1):
    chosen = start[:k]
    P = prod(chosen) + 1
    spf = smallest_prime_factor(P)
    print(f"{chosen} -> P={P}, новый простой делитель {spf}")

Вывод:

[2] -> P=3, новый простой делитель 3
[2, 3] -> P=7, новый простой делитель 7
[2, 3, 5] -> P=31, новый простой делитель 31
[2, 3, 5, 7] -> P=211, новый простой делитель 211
[2, 3, 5, 7, 11] -> P=2311, новый простой делитель 2311
[2, 3, 5, 7, 11, 13] -> P=30031, новый простой делитель 59

Как работает под капотом

Обратите внимание на последнюю строку: $30031 = 59 \cdot 509$. Само $P$ здесь составное! Это частая иллюзия — будто $P = p_1 \cdots p_k + 1$ всегда простое. Нет. Важно другое: его простой делитель (59) не входит в исходный список. Именно это и нужно доказательству: новый простой существует, а вот само $P$ простым быть не обязано. Логика Евклида гарантирует не «новое простое = $P$», а «у $P$ есть простой делитель вне списка».

Частые ошибки

Главное заблуждение мы уже назвали: считать, что $P$ обязательно простое. Второе — думать, что доказательство «строит» все простые по порядку; оно лишь показывает, что список не может быть конечным. Третье — забывать про оговорку «всякое число больше 1 имеет простой делитель»: без неё рассуждение не замыкается.

Итог

Простых чисел бесконечно много (теорема Евклида).
Доказательство: $P = p_1 \cdots p_k + 1$ имеет простой делитель вне любого конечного списка.
Само $P$ может быть составным — важен лишь факт существования нового простого делителя.