Цикада.
Известно, что количество простых чисел бесконечно, то есть не существует самого большого простого числа. Евклид доказал это еще две тысячи лет назад. Другое, но очень простое доказательство таково: предположим, что ряд простых чисел не бесконечен. Тогда можно было бы все простые числа перемножить: 2 × 3 × 5 × 7 и так далее, вплоть до самого большого из них. Обозначим получившееся гигантское произведение буквой P и прибавим к нему 1. Теперь у нас есть только два варианта: либо число P + 1 простое, либо оно делится на какое-либо другое, меньшее простое число. Но если разделить P + 1 на любое из простых чисел в нашем списке (а он, как мы условились, включает в себя все существующие простые числа), в остатке всегда останется 1. Это значит, что либо число P + 1 тоже простое, либо оно имеет простой делитель, которого нет в списке. Таким образом, начав с предположения, что существует некое наибольшее простое число, мы пришли к противоречию. В логике и математике этот прием называется “доказательством от противного” (частный случай “доведения до абсурда”, reductio ad absurdum) – когда несостоятельность какого-либо утверждения доказывают, демонстрируя абсурдность его следствий. Значит, исходное предположение неверно, а стало быть, истинно противоположное ему утверждение: существует бесконечное множество простых чисел. Это последнее утверждение называется теоремой Евклида.
В древности математикам нелегко было высчитывать простые числа. В классической Греции точно знали, что 127 – простое, так как это вытекает из “Начал” Евклида. Возможно, были известны и другие, бо́льшие простые числа – до нескольких сотен, а то и тысяч. В эпоху Возрождения были найдены и существенно бо́льшие, среди них и 524 287, рассчитанное математиком Пьетро Катальди из Болоньи, известным охотником за простыми числами. После публикации трудов французского монаха XVII века Марена Мерсенна, посвятившего немало лет изучению чисел вида 2n – 1, где n – натуральное (называемых сегодня “числа Мерсенна”), поиск простых чисел сосредоточился именно в этом направлении. Числа Мерсенна – главные подозреваемые, поскольку вероятность, что любое выбранное наугад число из их ряда окажется простым, гораздо выше, чем у других случайных нечетных чисел аналогичной величины (хотя далеко не все числа Мерсенна простые). Первые несколько простых чисел Мерсенна (то есть чисел Мерсенна, которые одновременно являются простыми) – это 3, 7, 31 и 127. Находка Катальди – это девятнадцатое из чисел Мерсенна (M19) и седьмое из простых чисел Мерсенна. Прошло почти полтора столетия, прежде чем швейцарский математик Леонард Эйлер нашел в 1732 году большее простое число. Еще полтора века спустя, в 1876 году, рекорд поставил Эдуард Люка, доказавший, что 127-е число Мерсенна (M127), равное приблизительно 170 ундециллионам
[32], также является простым.
Хотя многие из чисел Мерсенна действительно простые, сам Мерсенн допустил в своих расчетах несколько ошибок. Например, он определил как простое число M67. Делители этого числа впервые нашел в 1903 году Фрэнк Нельсон Коул. 31 октября математика пригласили сделать часовой доклад в Американском математическом обществе. Во время лекции Коул, не говоря ни слова, подошел к доске и вручную сначала вычислил значение числа 267 – 1, а затем перемножил 139 707 721 и 761 838 257 287, продемонстрировав, что результаты совпадают, – и молча же вернулся на свое место под гром аплодисментов. Позже он признался, что на то, чтобы найти делители числа 267 – 1, у него ушло “три года воскресений”.
С 1951 года поиск простых чисел ведется исключительно с помощью компьютеров. Появление все более быстрых алгоритмов позволяет математикам вычислять все бо́льшие и бо́льшие простые числа Мерсенна. На момент написания этой книги самое большое известное простое число – M74207281, имеющее 22 338 618 знаков. Его вычислил 17 сентября 2015 года Кёртис Купер, профессор Университета Центрального Миссури, в рамках проекта GIMPS (Great Internet Mersenne Prime Search, “Масштабный интернет-проект по поиску простых чисел Мерсенна”) – добровольного совместного проекта распределенных вычислений, участники которого за двадцать с лишним лет его существования уже рассчитали пятнадцать самых больших простых чисел Мерсенна. По сложившейся традиции авторы открытия отметили свой успех, откупорив бутылку шампанского.
Итак, мы знаем, что такое простые числа, и доказали, что их ряд бесконечен. Нам известно, что в современном мире они могут приносить пользу и что они встречаются в природе. Но в области простых чисел еще много белых пятен: например, мы не знаем, верны ли определенные гипотезы. Одна из наиболее известных – проблема Гольдбаха, названная так в честь немецкого математика Христиана Гольдбаха. Гипотеза гласит, что любое четное число, большее двух, можно представить в виде суммы двух простых чисел. Для малых четных чисел это утверждение легко проверить: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7 и так далее. С помощью компьютеров были проверены и гораздо большие числа – правило не подвело ни разу. Однако до сих пор неизвестно, верна ли гипотеза Гольдбаха во всех случаях.
Другая недоказанная гипотеза касается пар простых чисел, отличающихся на 2: таких как 3 и 5 или 11 и 13, – их еще называют числами-близнецами. Гипотеза о числах-близнецах гласит, что таких пар – бесконечное множество, однако доказать истинность этого утверждения пока никому не удалось.
Пожалуй, самая большая загадка простых чисел связана с их распределением. Среди малых натуральных чисел простые встречаются очень часто, но с ростом значений – все реже и реже. Математиков интересует, с какой скоростью убывает плотность простых чисел и как много мы вообще способны узнать об их частоте в числовом ряду. Какой-то строгой закономерности в их появлении не наблюдается, но это вовсе не значит, что они выскакивают где попало. В своей книге “Рекорды простых чисел” (The Book of Prime Number Records) Пауло Рибенбойм формулирует это таким образом:
Можно с довольно хорошей точностью предсказать количество простых чисел, меньших N (особенно при больши́х значениях N); с другой стороны, в распределении простых чисел в коротких интервалах наблюдается некая заложенная случайность. Это сочетание “случайности” и “предсказуемости” приводит к тому, что распределению простых чисел свойственны одновременно и упорядоченность, и элемент неожиданности.
Загадка простых чисел волнует многие поколения математиков. А ведь кажется, куда проще – даже дети в начальной школе могут объяснить, что такое простые числа, назвать несколько первых из них и определить, простое число или нет. Вот и Агниджо заинтересовался простыми числами в очень раннем возрасте, а заодно и кое-какими из нерешенных проблем вокруг них. А со временем этот интерес привел к увлечению другими великими тайнами теории чисел.
