В погоне за простотой

Пожалуй, немного найдется в математике задач, которые привлекают ученых и любителей науки на протяжении тысячелетий. Одна из таких проблем - поиск простых чисел.

Экскурс в историю

Едва освоив четыре арифметических действия, люди стали интересоваться различными свойствами натуральных чисел. Почему некоторые числа делятся на меньшие без остатка, в то время как другие числа почти не имеют делителей? Особое внимание привлекали числа, делителем которых являлась только единица: 2, 3, 5, 7, 11, 13, 17, ... (само число не считалось своим делителем) - их назвали простыми. Еще Евклид в "Началах" привел изящное и короткое доказательство того, что простых чисел бесконечно много. По-видимому, именно с этого доказательства и началась погоня математиков за большими простыми числами.

Суть проблемы в том, что доказательство Евклида неконструктивно, то есть не позволяет ответить на самый естественный вопрос: будет ли очередное (нечетное) число простым или составным? Этот воз и ныне там: и в наше время для проверки на простоту большого числа, как правило, приходится делить его последовательно на все подряд небольшие простые числа. К счастью, есть некоторые исключения, и именно благодаря им математики и умеют доказывать простоту у некоторых огромных чисел.

Так или иначе, но гонка за простыми числами была очень и очень непростой. С появлением компьютеров задача отыскания больших простых чисел стала одним из любимых "орешков", на которых программисты проверяли возможности новой техники. Причина проста - нахождение очередного нового гигантского простого числа является достаточно объемной вычислительной задачей, и большинство успехов в этом направлении достигается не благодаря математическим открытиям, а из-за повышения производительности "железа".

О некоторых покоренных вершинах я и хочу рассказать. Приводимые мной числовые примеры взяты из списка "The largest known primes", подготовленного профессором Крисом Колдуэллом (caldwell@utm.edu) и находящегося на http://www.utm.edu/research/primes/largest.html

Числа Мерсенна

Так называют простые числа M(p)=2^p-1 в честь француза Марена Мерсенна, жившего в начале XVII века. Любой математик быстро сообразит, что M(p) бывает простым только тогда, когда само число p - простое. А верно ли обратное - то есть для любого ли простого p число M(p) будет простым? К сожалению, это не так - например, число M(11) составное: M(11)=2047=23*89. Сам М.Мерсенн нашел несколько первых простых чисел такого вида и сделал предположения о следующих простых числах. Несмотря на то, что частично его предположения оказались ошибочными, они привлекли к себе внимание лучших математиков того времени. Для проверки на простоту этих чисел был разработан специальный алгоритм - тест Люка-Лемера. Именно благодаря этому алгоритму стало возможным проверять простоту чисел, содержащих многие тысячи десятичных цифр! (Для справки: разложение на множители даже 100-значного числа требует огромных вычислительных мощностей и на существующей технике не может быть произведено за приемлемое время. Между прочим, на этом факте держатся почти все современные способы кодирования и шифрования информации).

Интерес к числам Мерсенна тесно связан с так называемыми совершенными числами (которыми и занимались древние греки) - числами, равными сумме своих делителей: 6=1+2+3, 28=1+2+4+7+14. Тот же Евклид умел доказывать, что если число M(p) простое, то 2^(p-1)*M(p) - совершенное.

Наибольшее известное простое число Мерсенна было найдено в ноябре 1996 года благодаря проекту GIMPS (Great Internet Mersenne Prime Search), объединившему усилия многих энтузиастов-одиночек. Этот рекорд - 2^1398269-1 - содержит более четырехсот двадцати тысяч цифр! Предыдущее достижение 2^1257787-1 было установлено двумя годами ранее и содержало на сорок тысяч цифр меньше.

Близнецы

Так называются пары простых чисел, оодно из которых на 2 больше другого: 3 и 5, 11 и 13, 1997 и 1999. До сих пор неизвестно, конечно или бесконечно множество простых чисел-близнецов. Самая большая (на сегодняшний день) пара близнецов была открыта в 1995 году: это числа 242206083*2^38880-1 и 242206083*2^38880+1.

Числа Ферма

Знаменитый французский математик Пьер Ферма также занимался поисками больших простых чисел. В частности, он выдвинул такую гипотезу: при всех значениях n числа F(n)=2^(2^n)+1 являются простыми. Первые четыре числа Ферма - 5, 17, 257 и 65537 - простые, но уже пятое число F(5)=2^32+1 является составным - делится на 641.

Других простых чисел Ферма так и не найдено. Однако при их поисках постоянно обнаруживаются все новые и новые простые числа - делители больших чисел Ферма. Например, простое число 3*2^213321+1 (в котором около 70 тысяч цифр) является делителем числа F(213319).

Числа Каллена

Еще одно множество простых чисел специального вида - n*2^n+1 или n*2^n-1. Наибольшее известное такое число - 98726*2^98726-1.

Репьюниты и палиндромы

Все предыдущие монстры были примечательны тем, что их совершенно невозможно не только запомнить, но и просто выписать. Однако я могу назвать огромное простое число, запись и запоминание которого не вызовет у вас почти никаких трудностей. Это число 111...11, состоящее из 1031 единицы. Подобные числа называют репьюнитами (от англ. repeat unit - повторение единицы). Остальные числа, записанные одинаковыми цифрами, называют репдигитами (repeat digit). Поскольку все репдигиты делятся на соответствующие репьюниты, новых простых чисел среди них нет. Впрочем, математики интересуются также и "почти репдигитами" - числами, в записи которых все цифры, кроме одной, одинаковые. Например, простое число 8*10^11336-1 начинается с семерки, за которой следует куча девяток. А вот еще простой "почти репьюнит" - 11...1911...1, слева и справа от девятки стоит по 874 единицы. Это число является к тому же и палиндромом, то есть читается одинаково слева направо и справа налево. А самый большой найденный палиндром, являющийся простым числом - 100...0146564100...01 (5901 нуль слева и столько же справа, - всего 11811 цифр. Забавно, что и количество цифр в этом числе тоже палиндром).

Факториальные числа

Доказательство бесконечности количества простых чисел, данное Евклидом, опирается на такое рассуждение: если это не так, то перемножим все простые числа и к результату прибавим 1. Получившееся число не может делиться ни на одно из перемноженных чисел, а значит, существуют и другие простые числа.

Такое вычисление на самом деле довольно часто приводит к новым простым числам. Обычно их называют факториальными. Рекорд - число 2*3*5*...*18523+1 (около 8000 цифр). Чуть большее количество знаков содержится в числе 3610!-1, которое также является простым.

Всякая всячина

Числа, которые имеют более тысячи цифр, профессор Колдуэлл называет гигантами. Вот еще несколько простых чисел-гигантов из его коллекции:

97532*10^1183-1 - число, записываемое только нечетными цифрами (а именно, 9753199...9);

5*2^240937+1 - наибольшее из известных простых чисел, не являющихся числом Мерсенна;

123456789*10^5125+1 - содержит все 10 цифр;

10^999+1150^3-1 - наименьшее из известных простых гигантов.

Если вас заинтересовал мой рассказ об увлекательной гонке за простыми гигантами, обязательно загляните на http://www.utm.edu/research/primes/prime.html. Там можно найти более подробную информацию. В частности, можно включиться в проект GIMPS - переписать программное обеспечение (под Windows 3.1, '95 и NT), которое позволит искать большие простые числа прямо на домашнем (или рабочем) компьютере. Кто знает, может быть, именно Вы, уважаемый читатель, окажетесь первым человеком, нашедшим простое число, в котором более миллиона цифр?