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

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

Две тысячи лет спустя аргумент по-прежнему обладает качеством хорошего фокуса. Вы видите каждый шаг ясно. Вы знаете точно, чем он кончится. И он всё равно бьёт.

Что такое простое число и почему вопрос важен

Простое число это целое число больше 1, единственные делители которого: 1 и оно само. Первые из них: 2, 3, 5, 7, 11, 13. Они сидят внутри целых чисел как атомы: каждое другое целое число строится умножением простых. Число 30, например, распадается на 2 умножить на 3 умножить на 5, и по существу это можно сделать лишь одним способом.

Раз простые числа являются строительными блоками всех целых чисел, естественно спросить: закончатся ли они когда-нибудь? Существует ли наибольшее простое, за которым иссякает источник? Ответ Евклида: нет, и путь, которым он его даёт, достаточно изящен, чтобы проследить за ним за один присест.

Исходное предположение: список полон

Аргумент является доказательством от противного. Вы начинаете с того, что даёте оппоненту всё, что он хочет.

Теперь, собрав все простые числа в этом списке, построим из них новое число.

Конструируем число, ломающее список

Это ключевой ход, и стоит замедлиться, чтобы понять, что он делает. Умножение всех перечисленных простых даёт число, на которое каждое из них делится без остатка. Прибавление 1 разрушает это одним ударом для всех.

При делении N на p1 получается остаток 1: произведение (p1 умножить на p2 умножить на ... умножить на pk) делится на p1, а прибавление 1 сдвигает остаток к 1. Та же логика применима к p2, к p3, к каждому простому числу из списка. Ни одно из них не делит N без остатка.

Противоречие

Контрпример, который делает доказательство честным

Здесь многие популярные изложения доказательства Евклида сбиваются с пути. Они утверждают, что N само всегда простое. Это не так, и различие важно.

Возьмём список 13. Произведение равно 2 умножить на 3 умножить на 5 умножить на 7 умножить на 11 умножить на 13, что составляет 30030. Прибавим 1 и получим N = 30031.

Является ли 30031 простым? Нет.

30031 = 59 умножить на 509.

Оба числа, 59 и 509, являются простыми, и ни одно из них не входит в список 13. Именно это и предсказывает доказательство: не то, что N простое, а то, что простые делители N отсутствуют в списке. В данном случае простые делители это 59 и 509, два простых числа, которые были упущены в конечном списке. Аргумент подтверждён, но подтверждение приходит от делителей, а не от самого N.

Что на самом деле говорит доказательство

Стоит остановиться на форме аргумента, потому что она необычно чиста.

Вы не строите пропущенное простое явно. Вы не ищете его. Вы доказываете, что оно должно существовать, показывая, что предположение об обратном ведёт в логический тупик. Простое число q, скрытое в делителях числа N, может оказаться лёгким для нахождения (как 59 и 509, если попробовать несколько небольших делителей числа 30031) или оно может быть огромным. Доказательству всё равно. Его сила в неизбежности: какой бы список вы ни передали, конструкция найдёт в нём пробел.

Это естественно связывается с другими доказательствами, движущимися по тому же духу «предположи обратное, смотри, как оно рушится». Диагональный аргумент Кантора использует ту же структуру в большем масштабе: предположи, что существует полный список вещественных чисел, и затем построй вещественное число, доказуемо отсутствующее в нём. Отзвук Евклида узнаваем.

Почему простые числа не иссякают полностью

Одна вещь, о которой доказательство не говорит, это насколько далеко друг от друга могут стоять простые числа или сколь велико следующее простое после любого заданного. Аргумент Евклида гарантирует лишь существование: где-то за пределами любой конечной совокупности живёт ещё одно простое. Распределение простых чисел по числовой прямой это намного более трудный вопрос, остающийся одной из глубочайших открытых проблем математики по сей день.

Что доказательство говорит, так это структурное. Простые числа не могут быть исчерпаны никакими конечными средствами. Вы могли бы посвятить жизнь составлению списка простых чисел, и всегда перечисляли бы в бесконечный остаток. Каждое найденное вами простое было реальным, но те, что ждали впереди, были столь же реальны, столь же многочисленны и столь же недостижимы конечным списком.

Для понимания того, как быстро растут числа при построении через умножение и степени, статья о понимании степеней интуитивно является естественным дополнением: произведение p1 умножить на p2 умножить на ... умножить на pk растёт быстрее, чем можно ожидать, и именно этот рост объясняет, почему N так быстро становится таким большим.

Дзен этого

Доказательству Евклида более двух тысяч лет, и математики с тех пор нашли сотни доказательств того же результата. Ни одно из них не сделало это устаревшим. Оно сохраняет своё место не потому что оно хитрейшее или наиболее общее, а потому что оно наиболее прозрачное.

Вы видите весь аргумент за один проход. Конструкция естественна. Противоречие остро. Нет ни одного шага, где нужно принять что-то на веру или доверять, что сложная машина делает то, что заявляет.

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

Этого достаточно. Этого всегда было достаточно.

Другие результаты, разделяющие этот дух неизбежности: теорема Гудстина показывает последовательность, которая всегда возвращается к нулю, несмотря на рост за все записуемые пределы, используя ту же логику «что-то должно произойти, потому что альтернатива невозможна». Это семейство аргументов стоит знать. Каждый из них это разный угол на один и тот же основополагающий факт: в математике нет лазеек. Структура держит.