Восемь этюдов о бесконечности. Математическое приключение - Хаим Шапира

Образуем новое число S, такое, что S = (2 × 3 × 5 × 7 × 11 × … × P) + 1.

Число либо S является простым, либо делится на одно или несколько из простых чисел, больших, чем P. В любом из этих случаев число P не может быть самым большим простым числом. Следовательно, количество простых чисел должно быть бесконечным.

Ч. т. д.

Убедило ли вас это доказательство? Если да, вы можете пропустить следующее; если нет, – читайте дальше!

Длинное доказательство

Здесь мы тоже предположим существование в списке простых чисел самого большого числа, а потом докажем, что такое положение невозможно, что докажет, что простые числа бесконечны. Доказательство этого типа, в котором сначала выдвигают некоторое предположение, а затем доказывают, что такое положение вещей невозможно, математики называют «доказательством от противного». Хотя эта простая, но изящная концепция кажется математикам совершенно естественной, многим, впервые столкнувшимся с ее идеей, бывает несколько трудно с ней примириться.

Если количество простых чисел конечно, то должна существовать возможность найти самое большое простое число, которое мы обозначим P. Выпишем все простые числа: 2, 3, 5, 7, 11, 13, 17, …, P.

Теперь образуем еще одно число: S = (2 × 3 × 5 × × 7 × 11 × 13 × 17 ×… × P) + 1. Другими словами, число S равно произведению всех простых чисел из нашего списка плюс 1.

На что же делится число S?

Оно не может делиться на два, так как выражение в скобках равно четному числу (поскольку 2 – один из сомножителей этого выражения). Прибавление единицы делает S нечетным числом.

Кроме того, S не может делиться на 3. Это можно утверждать по такой же причине: число, стоящее в скобках, делится на 3 (потому что 3 – один из сомножителей этого выражения); следовательно, при прибавлении единицы получается число, не делящееся на 3 (собственно говоря, при делении S на любое простое число из списка получается остаток, равный 1).

Число S также не может делиться на 4, поскольку оно не делится на 2. Вообще, любое число, делящееся на некий делитель, также делится и на его простые сомножители. Например, любое число, делящееся на 6, делится также на 2 и на 3.

Продолжая в том же духе, мы поймем, немного поразмыслив, что число S не может делиться ни на 5, ни на 6, ни на 7, ни на какое бы то ни было другое число до числа P включительно, которое, как мы предполагаем, является самым большим простым числом. Это оставляет нам две возможности:

1. Либо S – простое число, большее P.

2. Либо S делится на некое простое число, не входящее в наш список, то есть на простое число, большее P (поскольку мы уже видели, что оно не делится ни на одно из простых чисел, меньших или равных P).

Какой бы вариант мы ни выбрали, мы в любом случае приходим к противоречию с нашим исходным утверждением, а именно, что число P – самое большое простое число. Если же предположение о том, что P – самое большое простое число, приводит к противоречию, значит, самого большого простого числа не существует.

Ч. т. д.

Важное примечание: доказательство Евклида не особенно конструктивно. Иначе говоря, оно не дает простого рецепта получения новых простых чисел. Число S, как мы уже указывали, вполне может не быть простым числом: оно также может быть числом составным, делящимся на простое число, большее P.

Вот иллюстрация этого утверждения.

Предположим, что число 3 – самое большое из существующих простых чисел (разумеется, это предположение абсолютно ложно). Образуем число S, равное (2 × 3) + 1 = 7, и 7 действительно оказывается простым числом. То же верно и для S = (2 × 3 × 5) + 1, для S = (2 × 3 × 5 × 7) + 1 и для S = (2 × 3 × 5 × 7 × 11) + 1.

Но после этого мы получаем пример осуществления второго варианта:

Другими словами, (2 × 3 × 5 × 7 × 11 × 13) + 1 есть составное число, делящееся на простые числа 59 и 509, которые оба больше числа 13, которое временно выступало в роли «самого большого простого числа». Видим, что никакого противоречия в доказательстве Евклида нет – оно безупречно.

Интересно отметить, что довольно многим впервые столкнувшимся с доказательством Евклида кажется, что, если бы им его не показали, они вполне смогли бы открыть его самостоятельно. «Подумаешь, перемножить простые числа и прибавить единицу. Что тут сложного? Я бы и сам до этого додумался за пару минут, не больше!» В большинстве случаев это иллюзия. Простота этого доказательства лишь подчеркивает его красоту и гениальность.

Я встречал выдающихся математиков, убежденных, что предложенное Евклидом доказательство бесконечности простых чисел – одна из самых прекрасных теорем во всей истории математики. Будь и я выдающимся математиком, я бы тоже, несомненно, присоединил мой голос к их хору.

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

Число, носящее почетный титул «самого большого простого числа, открытого до 2018 г.», равно 277 232 917 – 1[17]. Я не советовал бы вам пытаться сосчитать это число и выписать его в тетради: в ней просто не хватит для этого страниц. Если учесть, что количество атомов во Вселенной меньше, чем 2320, наверное, можно составить некоторое представление о том, насколько огромно число 277 232 917 – 1. В нем 23 249 425 знаков – почти на миллион (!) больше, чем в числе, которое считалось самым большим простым числом до него: то было открыто в январе 2016 г., и его значение – 274 207 281 – 1 (в этом числе «только лишь» 22 338 618 знаков). При этом число 2320 всего-то 96-значное. Все относительно!