Тайны простых чисел. Фрагмент книги "Эта странная математика"
Книга Дэвида Дарлинга и Агниджо Банерджи "Эта странная математика. На краю бесконечности и за ним" (перевод Алексея Глущенко) подробно и доходчиво объясняет, из каких формул, законов и числовых последовательностей состоит наш мир и как нам могут помочь эти знания. Делимся с вами фрагментом из книги, рассказывающем о тайнах простых чисел.
Простое число — это всего лишь натуральное число, которое делится без остатка только на само себя и на единицу. Казалось бы, ничего особенного в таком свойстве нет, и тем не менее простые числа в математике — на особом положении. Не будет преувеличением сказать, что простые числа связаны с некоторыми из величайших неразгаданных тайн в этой науке и играют важную роль в нашей повседневной жизни. Например, каждый раз, когда вы пользуетесь кредитной карточкой, компьютеру банка нужно удостовериться, что вы ее владелец. Делает он это с помощью алгоритма, который превращает очень большое число в однозначно определяемое произведение двух заранее известных простых множителей. От решения таких странных задачек во многом зависит наша финансовая безопасность.
Первые несколько простых чисел — это 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29. Все числа, не относящиеся к простым, называют составными. Само число 1 простым не считается (а могло бы), поскольку иначе возникли бы сложности с рядом полезных теорем, в том числе с той, которая настолько важна, что ее величают "основной теоремой арифметики". Она гласит, что любое число можно представить в виде произведения простых чисел единственным способом (если не учитывать порядок следования множителей). Например, 10 = 2 × 5, а 12 = 2 × 2 × 3. Если бы единица считалась простым числом, то таких способов было бы бесконечное множество — ведь можно сколько угодно раз последовательно умножать число на единицу, результат от этого не изменится.
В природе простые числа встречаются в самых удивительных и неожиданных местах. Один из видов цикад, Magicicada septendecim, имеет 17-летний жизненный цикл. Все особи этого вида проводят в стадии личинки ровно семнадцать лет, после чего вся популяция одновременно вылупляется из своих оболочек для спаривания. Другой вид, Magicicada tredecim, имеет 13-летний жизненный цикл. Существует множество теорий, почему в процессе эволюции у этих цикад выработался жизненный цикл, выражающийся простым числом лет. Самая популярная заключается в том, что существовал хищник, тоже появлявшийся раз в определенное количество лет. Если бы цикады достигали зрелости в один год с питающимися ими животными, весь выводок этих насекомых, скорее всего, тут же уничтожался бы. Выживание цикад зависело от способности выработать жизненный цикл, минимально пересекающийся с циклом хищников. Если бы, например, цикл развития того или иного вида составлял пятнадцать лет, то хищники вполне могли бы появляться каждые три года или пять лет и пожирать выводок насекомых всякий раз при его вылуплении; либо появляться каждые шесть или десять лет и уничтожать новое поколение цикад через раз. И в том и в другом случае данный вид цикад в скором времени просто вымер бы. Другое дело, когда жизненный цикл цикад длится семнадцать лет: хищники с более короткой продолжительностью жизни (а по имеющимся данным, гипотетические хищники жили не так долго, как цикады) шестнадцать своих циклов не будут заставать время появления лакомой добычи и в конце концов просто вымрут от истощения. Такие хищники давно бы уже исчезли с лица земли, оставив цикад с их жизненным циклом, выражающимся простым числом лет, живыми-здоровыми.
Известно, что количество простых чисел бесконечно, то есть не существует самого большого простого числа. Евклид доказал это еще две тысячи лет назад. Другое, но очень простое доказательство таково: предположим, что ряд простых чисел не бесконечен. Тогда можно было бы все простые числа перемножить: 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 ундециллионам, также является простым.
Хотя многие из чисел Мерсенна действительно простые, сам Мерсенн допустил в своих расчетах несколько ошибок. Например, он определил как простое число 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); с другой стороны, в распределении простых чисел в коротких интервалах наблюдается некая заложенная случайность. Это сочетание "случайности" и "предсказуемости" приводит к тому, что распределению простых чисел свойственны одновременно и упорядоченность, и элемент неожиданности.
Загадка простых чисел волнует многие поколения математиков. А ведь кажется, куда проще — даже дети в начальной школе могут объяснить, что такое простые числа, назвать несколько первых из них и определить, простое число или нет. Вот и Агниджо заинтересовался простыми числами в очень раннем возрасте, а заодно и кое-какими из нерешенных проблем вокруг них. А со временем этот интерес привел к увлечению другими великими тайнами теории чисел.
Простые числа — это еще и своего рода атомы числовой вселенной, из которых строятся все остальные натуральные числа. Казалось бы, есть все основания надеяться, что они будут подчиняться строгим законам — и предсказывать, где именно в числовом ряду появится следующее, не будет составлять никакого труда. Но нет, эти математические кирпичики поразительно непослушны и капризны. Именно это противоречие между ожиданием и реальностью, стойкое ощущение, что некие организующие принципы чрезвычайной важности находятся за пределами нашего разумения, не давало покоя математикам с античных времен.