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

Предположим, что ряд 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.