Теорема (основная теорема арифметики). Любое положительное целое (натуральное) число может быть разложено на простые множители единственным образом (если пренебречь порядком множителей)[18].
(Здесь необходимо небольшое пояснение. В случае, скажем, числа 30 это утверждение достаточно ясно. Мы можем представить 30 как 2 × 3 × 5 или как 5 × 3 × 2 – разницы нет, отличается лишь порядок множителей. Простое число имеет всего один простой множитель – само себя. Например, множитель 13 – это 13. Но как быть с 1? Принято говорить, что пустое произведение[19] равно единичному элементу; таким образом, произведение отсутствующих элементов равно 1.)
Сочетая простые числа, мы выстраиваем все положительные целые числа. Простые числа – это атомы умножения.
Насколько много?
Вернемся к вопросу: сколько всего простых чисел существует? Ответ – на следующей строчке.
Теорема. Простых чисел бесконечно много.
Утверждение приписывают Евклиду[20]. Доказательство этой теоремы – математическая жемчужина. Мы не можем доказать ее методом перебора. Очевидно, что время от времени в числовом ряде попадаются простые числа. Вот несколько первых простых чисел:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 и 67.
Но чем дальше мы идем по последовательности простых чисел, тем обширнее становятся промежутки между ними. Если посмотреть на перечень выше, можно увидеть, что два числа отстоят друг от друга максимум на 6 единиц (например, 53 и 59). Но простые числа 89 и 97 отстоят друг от друга на 8 единиц, все целые числа между ними составные. Или вот другой пример: 139 и 149 – их отделяет 10 единиц. Чем дальше мы двигаемся, тем быстрее увеличиваются промежутки между соседними простыми числами. Можно предположить, что в конечном итоге простые числа должны совсем исчезнуть. На самом деле, хотя они и встречаются все реже, их список в числовом ряду не имеет конца. Впрочем, прежде чем говорить об этом уверенно, мы должны привести доказательство.
Ключевая идея – задаться вопросом: а что, если?..
А что, если количество простых чисел конечно? Если мы продемонстрируем, что предположение: «Количество простых чисел конечно» – приводит к абсурдному выводу, то будем считать его ложным[21]. Вслед за Шерлоком Холмсом мы найдем истину, отбросив невозможные варианты, и у нас получится, что простых чисел бесконечно много.
Вот что нам надо будет сделать:
1. Предположить, что количество простых чисел конечно;
2. Показать, что это предположение ведет к невозможному выводу;
3. Сделать умозаключение, что, раз предположение ведет к логическому противоречию, оно ложно;
4. Вывести из этого, что простых чисел бесконечно много.
А теперь перейдем к делу. Предположим, что простые числа можно пересчитать, и посмотрим, к чему это приведет.
Если количество простых чисел конечно, должно существовать наибольшее простое число P – крайнее в ряду простых чисел. В таком случае полный перечень простых чисел будет выглядеть так:
2, 3, 5, 7, 11, 13, …, P.
Перемножим все эти числа и приплюсуем единицу. Назовем получившееся гигантское число N:
N = (2 × 3 × 5 × 7 × 11 × 13 × … × P) + 1.
Число N – простое[22]? Наше предположение заставляет нас ответить: нет, потому что N больше P, последнего простого числа. Значит, N – составное число, и его можно разложить на множители. Здесь мы попадаем в западню.
Мы знаем, что у N есть простые делители. Может ли таким делителем быть 2? Мы утверждаем: нет. Посмотрите на формулу для вычисления N и обратите внимание, что число в скобках четное, потому что среди множителей присутствует 2:
N = (
2
× 3 × 5 × 7 × 11 × 13 × … ×
P) + 1.
Таким образом, N на единицу больше некоторого гигантского четного числа. Другими словами, N – нечетное, следовательно, оно не делится на 2.
Ну и ладно. Мы же знаем, что у N есть простой делитель, так что нет ничего страшного в том, что 2 не подходит. Как насчет 3? Посмотрим снова на число в скобках и обнаружим, что среди множителей есть 3:
N = (2 ×
3
× 5 × 7 × 11 × 13 × … ×
P) + 1.
Таким образом, N на единицу больше некоторого гигантского числа, делящегося на 3. Это означает, что при вычислении частного N / 3 мы получим остаток 1. Следовательно, N не делится на 3.
Видите, куда мы движемся? Возьмем очередное простое число, 5. Мы утверждаем, что N не делится на 5, потому что оно на единицу больше числа, без остатка делящегося на 5:
N = (2 × 3 ×
5
× 7 × 11 × 13 × … ×
P) + 1.
Точно так же мы доказываем, что N не делится ни на 7, ни на 11, ни на 13 и ни на какое угодно другое простое число!
К чему мы пришли? Наше предположение о том, что количество простых чисел конечно, привело нас к двум выводам:
– N делится на некое простое число;
– N не делится ни на какое простое число.
Но это же абсурдно! Из ловушки можно выбраться, только если признать, что предположение о конечном количестве простых чисел было ложным. Таким образом, получается, что простых чисел бесконечно много.
Конструктивный подход
Представленное нами доказательство относится к разряду доказательств от противного. Мы предположили, что утверждение, обратное тому, которое мы хотим доказать, верно, затем продемонстрировали, что это приводит к безвыходной ситуации, после чего сделали умозаключение, что наше предположение ложно, а утверждение, требующее доказательства, истинно. Путеводная путаница, софистика-эквилибристика!
Есть и другой способ доказательства: создать некий механизм по производству простых чисел. Мы засыпаем в него пригоршню простых чисел и – вуаля! – оттуда высыпаются новые простые числа. Вот как работает эта машина.
Зачерпнем полдюжины простых чисел: 2, 3, 5, 7, 11 и 13. Перемножим их и приплюсуем единицу:
(2 × 3 × 5 × 7 × 11 × 13) + 1 = 30 031.
Ясно, что 30 031 не делится на 2, – это легко заметить, потому что последняя цифра нечетная. На 3 оно тоже не делится (потому что на единицу больше, чем 2 × 3 × 5 × 7 × 11 × 13, которое делится на 3). Точно так же оно не делится на 5, 7, 11 и 13. Стало быть, или это число само простое, или его можно разложить на простые множители, не входящие в наш перечень. Кости выпали так, что число 30 031 – составное. Оно раскладывается на простые множители следующим образом: 59 × 509. Этих чисел не было в нашем перечне.
Возьмем их и предыдущие полудюжины чисел и построим новое число:
(2 × 3 × 5 × 7 × 11 × 13 × 59 × 509) + 1,
что равно 901 830 931. Кости выпали так, что число оказалось простым[23].
Мы можем добавить его в наш перечень и наштамповать так еще много чисел – либо простых, либо разложимых на простые множители. Эта операция позволяет бесконечно получать все новые и новые простые числа.
Другое доказательство
Это не единственное доказательства того, что простых чисел бесконечно много. Вот вам еще одно.
Как и в первом доказательстве, предположим, что количество простых чисел конечно, и покажем, что это предположение ведет к противоречию. Представим, что самое большое простое число равно P, и составим перечень простых чисел:
