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

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

Ч. т. д.

Кстати, если вам интересно, используемое во многих языках вместо «ч. т. д.» сокращение QED происходит от латинских слов Quod Erat Demonstrandum, то есть «что и нужно было продемонстрировать»: каждый математик гордо выписывает это радостное обозначение в конце своего рассуждения, когда ему наконец удается довести до завершения какое-нибудь длинное и сложное доказательство.

Спиноза часто использовал это латинское сокращение. Интересно отметить, что сам Евклид применял греческое сокращение OEΔ, внешне похожее на латинское и означающее ὅπԑρ ἔδει δεῖξαι – «что и нужно было показать».

Важное примечание: доказательство Евклида не особенно конструктивно. Иначе говоря, оно не дает простого рецепта получения новых простых чисел. Число 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 = 30 031 = 59 × 509.

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

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

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

Числа Мерсенна и Книга рекордов Гиннесса

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

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

Кстати говоря, доказательство того, что это чудовищное число относится к простым числам, было получено не живым математиком из плоти и крови, а сетевым вычислительным проектом под названием GIMPS (Great Internet Mersenne Prime Search – «Великий интернет-поиск простых чисел Мерсенна»).

Что же такое «число Мерсенна»? Возможно, правильнее было бы спросить иначе: кто такой Мерсенн? Числа вида 2ⁿ – 1 называют числами Мерсенна в честь французского философа, богослова, музыковеда и математика Марена Мерсенна (1588–1648). Если вам кажется, что перечень его титулов недостаточно впечатляющ, позвольте мне добавить еще один: Мерсенн был первым человеком, измерившим скорость звука.

Все ли числа Мерсенна простые? Вовсе нет.