Математика · объяснение и практика

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

Понимаем доказательство бесконечности простых через произведение конечного списка плюс один и отделяем новый делитель от самого построенного числа.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

Главная мысль

Для любого конечного списка простых возьмём их произведение и прибавим единицу. Полученное число не делится ни на одно простое из списка. Оно имеет простой делитель, значит, список не мог содержать все простые числа.

Как превратить список в проверяемое условие

Представим, что кто-то выписал все простые числа в конечную строку p₁, p₂, …, pₖ. Не требуется знать, насколько длинна эта строка и какое число в ней последнее. Достаточно построить число N = p₁p₂…pₖ+1. При делении N на каждый множитель из списка остаток равен единице.

Поэтому ни один перечисленный простой не является делителем N. При этом N больше единицы, а любое такое натуральное число имеет хотя бы один простой делитель: если само число составное, его можно последовательно раскладывать на меньшие множители. Найденный простой делитель не принадлежит исходной строке. Предположение о полноте конечного списка оказывается неверным.

Почему новое число не обязано быть простым

В доказательстве часто теряется важное различие: новым гарантированно является некоторый простой делитель N, а не обязательно само N. Проверка небольших произведений создаёт впечатление, что прибавление единицы всегда даёт простое. Однако конечное число удачных примеров не устанавливает такого правила, и для доказательства бесконечности это правило вовсе не нужно.

Возьмём список 2, 3, 5, 7, 11, 13. Его произведение равно 30030, а N = 30031 = 59·509. Построенное число составное, но оба указанных множителя отсутствуют в исходном списке. Достаточно даже проверить, что 59 — новый простой делитель: у него нет простых делителей среди 2, 3, 5 и 7, а √59 меньше восьми.

Пример

Список содержит только 2, 5 и 11. Как построить число, не делящееся ни на одно из них?

Произведение равно 110, поэтому берём 111. Оно делится на 3 и 37, но не на 2, 5 или 11. Число 111 не простое; зато делитель 3 уже показывает неполноту списка.

Чем доказательство отличается от поиска следующего простого

Построение отвечает на вопрос о невозможности закончить список. Оно не обязано находить ближайшее простое после последнего выписанного числа и не обещает удобного вычислительного алгоритма для очень больших произведений. Разложение N может оказаться трудным, но существование простого делителя обеспечено независимо от скорости его нахождения.

Если конечный список имеет пропуски, новый делитель может быть меньше его наибольшего элемента. Поэтому вывод «найдётся простое больше всех записанных» удобнее делать для списка всех простых до заданной границы. Для произвольного списка точный вывод другой: найдётся простое вне списка. Такая аккуратность сохраняет силу рассуждения и не добавляет к нему недоказанное расположение нового числа.

От чтения к действию

А теперь — вы

Число N построено как произведение всех простых из конечного списка плюс 1. Что гарантировано?

Частые вопросы

Можно прибавить единицу к сумме простых?

Такая сумма не гарантирует остаток 1 при делении на каждый элемент. Для стандартного построения важно именно произведение.

Нужно разложить огромное N, чтобы закончить доказательство?

Нет. Для логического вывода достаточно существования простого делителя. Явное разложение нужно лишь для конкретного числового примера.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться