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

Но вернемся к Евклиду. Прежде чем мы посмотрим его ответ на вопрос «сколько существует простых чисел?», давайте немного подумаем самостоятельно.

Прежде всего нам необходимо определить, конечно или бесконечно количество простых чисел.

Если их количество конечно, то каково самое большое простое число?

Если же простых чисел бесконечно много, можно ли это доказать?

Можно ли представить себе, что некое действительно огромное, необычайно большое число не делится нацело ни на что, кроме единицы и самого себя, и, следовательно, считается простым числом?

Существует ли формула, которую можно использовать для получения всех простых чисел?

Существует бесконечно много простых чисел.

Я приведу два доказательства этой теоремы. Одно из них кратко и подчеркивает красоту великой идеи Евклида. Второе доказательство, по сути, сводится к тому же, но оно длиннее и помогает подробно объяснить более краткое доказательство.

Предположим, что ряд 2, 3, 5, 7, 11, …, P – это полный список простых чисел вплоть до некоторого простого числа P .

Образуем новое число 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 – самое большое простое число, приводит к противоречию, значит, самого большого простого числа не существует.

Ч. т. д.

Кстати, если вам интересно, используемое во многих языках вместо «ч. т. д.» сокращение 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, которое временно выступало в роли «самого большого простого числа». Видим, что никакого противоречия в доказательстве Евклида нет – оно безупречно.

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

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