Простых чисел бесконечно много: доказательство, которому 2300 лет

Если простые числа когда-нибудь заканчиваются, перемножьте их все, прибавьте единицу — и вы только что их обманули.

Доказательство Евклида не вычисляет «самое большое простое число». Оно показывает, что такого числа в принципе быть не может.

Кто такие простые и почему они особенные

Простое число — это натуральное число больше единицы, которое делится только на единицу и на само себя: 2, 3, 5, 7, 11, 13... Числа вроде 6 = 2·3 или 12 = 2·2·3 называют составными, потому что их можно разложить на множители помельче.

Простые — это «атомы» арифметики. Основная теорема арифметики утверждает: любое натуральное число раскладывается на простые множители ровно одним способом (если не считать порядок). Поэтому понять простые — значит понять кирпичики, из которых сложены все остальные числа.

Но есть подвох. Чем дальше мы идём, тем реже встречаются простые. До 100 их 25 штук, а вот между 10 000 000 и 10 000 100 может не оказаться ни одного. Возникает естественный страх: а вдруг они всё-таки иссякнут?

Хитрость Евклида: доказательство от противного

Греческий математик Евклид около 300 года до нашей эры предложил рассуждение, которое работает наоборот. Вместо того чтобы искать простые, он предположил, что их конечное число, — и получил абсурд.

Допустим, простых чисел всего конечное количество. Тогда мы можем выписать их все в один список:

$$p_1, p_2, p_3, \ldots, p_n$$

где $p_n$ — то самое «последнее, самое большое простое». Теперь Евклид строит новое число — перемножает их все и прибавляет единицу:

$$N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1$$

Что не так с этим числом N

Число $N$ либо простое, либо составное — третьего не дано. Рассмотрим оба случая.

Случай первый: $N$ простое. Но оно явно больше любого $p_i$ из нашего списка, ведь мы перемножили их все и ещё прибавили единицу. Значит, мы нашли простое, которого в «полном» списке нет. Противоречие — список был неполным.

Случай второй: $N$ составное. Тогда оно делится на какое-то простое число. Но попробуйте поделить $N$ на любое $p_i$ из списка — всегда останется остаток 1! Ведь произведение $p_1 \cdots p_n$ делится на каждое $p_i$ нацело, а мы прибавили единицу сверху. Значит, простой делитель числа $N$ не входит в наш список. Снова противоречие.

Почему это гениально

Обратите внимание: Евклид не сказал, что $N$ обязательно простое. Это частое заблуждение. Он сказал лишь, что у $N$ есть простой делитель, которого нет в списке, — а этого достаточно, чтобы обрушить предположение о конечности.

Проверим на маленьком примере. Возьмём список из первых простых: 2, 3, 5, 7, 11, 13. Перемножим и прибавим единицу:

$$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031$$

Само число 30031 не простое: $30031 = 59 \cdot 509$. Но смотрите — 59 и 509 простые, и их не было в нашем списке! Алгоритм честно вывел нас на новые простые.

def smallest_prime_factor(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return d
        d += 1
    return n

primes = [2, 3, 5, 7, 11, 13]
N = 1
for p in primes:
    N *= p
N += 1
print("N =", N)
print("Простой делитель N:", smallest_prime_factor(N), "— его не было в списке!")

Эхо длиной в тысячелетия

Эта идея — предположить конечность и упереться в противоречие — стала образцом математического мышления. Спустя века появились другие доказательства бесконечности простых: через ряды (Эйлер связал их с гармоническим рядом), через топологию (Фюрстенберг придумал доказательство на языке открытых множеств), через числа Ферма. Но аргумент Евклида остаётся самым прозрачным.

Бесконечность простых — не очевидный факт, который «и так понятно». Это утверждение, которое пришлось доказать, и красота в том, что доказательство уместилось в несколько строк и не устарело за двадцать три столетия.