Представленное нами доказательство относится к разряду доказательств от противного. Мы предположили, что утверждение, обратное тому, которое мы хотим доказать, верно, затем продемонстрировали, что это приводит к безвыходной ситуации, после чего сделали умозаключение, что наше предположение ложно, а утверждение, требующее доказательства, истинно. Путеводная путаница, софистика-эквилибристика!
Есть и другой способ доказательства: создать некий механизм по производству простых чисел. Мы засыпаем в него пригоршню простых чисел и – вуаля! – оттуда высыпаются новые простые числа. Вот как работает эта машина.
Зачерпнем полдюжины простых чисел: 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, и составим перечень простых чисел:
2, 3, 5, 7, 11, 13, …, P.
Пусть N – результат перемножения всех этих чисел:
N = 2 × 3 × 5 × 7 × 11 × 13 × … × P.
Теперь давайте подумаем обо всех числах от 1 до N включительно. Каждое из них (за исключением 1) делится на одно или несколько простых чисел; иными словами, любое число (кроме 1) делится на какое-то простое число.
Сколько чисел от 1 до N делится на 2? Очевидно, что половина (четные числа). Вычеркнем их и оставим лишь нечетные:
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, …
Количество целых чисел между 1 и N, которые мы вычеркнули, равно N / 2.
Вычеркнем из оставшихся чисел те, которые делятся на 3. Вот что получится:
1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, …
Мы удалили треть оставшихся чисел[24]. Осталось две трети, а от изначального количества –
Продолжим в том же духе и вычеркнем числа, делящиеся на 5, удалив таким образом пятую часть оставшихся чисел. Получится чисел. Вот что останется:
1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, …
Дальше мы вычеркиваем числа, делящиеся на 7, оставив шесть седьмых от нашего перечня, и будем двигаться по этому пути, пока не дойдем до числа P.
В конце концов количество тех чисел, которые мы не вычеркнули, станет равно
Так как все числа от 1 до N, кроме 1, делятся на какое-то простое число, выражение (C) должно быть равно 1. Верно? Вспомним, что N = 2 × 3 × 5 × 7 × 11 × 13 × … × P, подставим это произведение в выражение (C) и перегруппируем множители:
Это дает 1 × 2 × 4 × 6 × … × (P – 1), что существенно больше 1! Выражение (C) должно быть равно 1, но очевидным образом не равно 1. Ошибка заключалась в изначальном предположении о том, что количество простых чисел конечно. Следовательно, их бесконечно много.
Две сложные задачиЕсть много захватывающих вопросов о простых числах. Здесь я расскажу про две самые печально известные проблемы.
Хотя простых чисел бесконечно много, они встречаются все реже и реже, когда мы последовательно двигаемся от единицы к бесконечности. Позже (в главе 7) мы проанализируем среднюю разность между двумя соседними большими простыми числами. Однако простые числа все равно часто встречаются рядом, отличаясь на две и более единицы (единственная пара с отличием на один – 2 и 3). Если простые числа отличаются на две единицы, их называют простыми числами-близнецами, или парными простыми числами. Наименьшая пара близнецов – числа 3 и 5. Между 1 и 10 000 есть 205 пар близнецов, последние – числа 9929 и 9931.
Вопрос: простых чисел-близнецов бесконечно много?
Надо признать, что это неизвестно до сих пор.
Вот другой вопрос. Принято считать, что впервые его поставил немецкий математик Кристиан Гольдбах (1690–1764). Ему стало любопытно: какие четные числа (кроме 2) можно представить в качестве суммы двух простых? Вот пример:
Вопрос: можем ли мы продолжать этот ряд бесконечно? Гольдбах предположил, что любое четное число (за исключением 2) представляет собой сумму двух простых.
Но на самом деле мы до сих пор не знаем этого наверняка.
Применение простых чисел в криптографииИзучение простых чисел относится к области математики под названием теория чисел. Британский математик Годфри Харди говорил: «До сих пор никто не обнаружил, как применить теорию чисел в военных целях».
Харди не мог предвидеть появления глобальной компьютерной сети и того факта, что безопасность в сети будет зависеть от простых чисел. Каким образом?
Пусть P и Q – два больших простых числа, скажем стозначных. Перемножить их – титанический труд для человека, но компьютер может посчитать произведение N = P × Q мгновенно. В то же время мы угодим в тупик, если попытаемся выяснить, какие два простых множителя дают N при умножении. Никто не знает эффективного алгоритма разложения таких огромных чисел на простые множители[25].
(Как это ни странно, определить, простое число или составное, можно достаточно быстро; однако найти простые множители больших чисел совсем не просто.)
Удивительно, однако эта диспропорция – легко перемножить, сложно разложить на множители – легла в основу
