Загадки простых чисел. (первая серия)

Загадки простых чисел (первая серия)

Какое число называется простым?

Некоторые числа могут быть получены при перемноже­нии двух меньших чисел, к примеру: 6= 2 х 3. Другие, такие как 5, невозможно разложить подобным образом на сомножители. Максимум, что можно сделать, это записать 5 = 1 х 5, но в этом выражении нет двух меньших чисел. Числа, которые можно разбить на сомножители, называют составными, а те, что разложить невозможно, — простыми. Простые чис­ла кажутся такой несложной темой! Простые числа — пер­вичные строительные кирпичики для всех натуральных чисел, и обнаружить их можно в самых разных разделах математики. Но в них есть тайна – они раскиданы сре­ди положительных целых чисел случайным образом. Это естественное следствие их определения — ведь определяются они не через какое-либо присущее им свойство, а напротив — через свойство, которое у них отсутствует.

Некоторые свойства простых чисел очевидны.

• За исключением самого маленького из них, двойки, все они нечетные.
• Сумма цифр простого числа, за исключением тройки, не может быть кратна трем.
• Они, за исключением пятерки, не могут заканчиваться на цифру 5.

Если же число не подпадает под эти правила — и под несколько других, более тонких, — то невозможно посмотреть на него и сразу сказать, простое это число или нет.

За тысячелетия математики сумели постепенно расширить свои знания о простых числах. Время от времени и сегодня решаются новые серьезные проблемы, с ними связанные. Однако многие вопросы по-прежнему остаются нерешенными. Некоторые из них фундаментальны и легко формулируются, другие понятны немногим.

Как представить заданное число в виде произведения простых чисел?

Как ни удивительно, определить, является ли данное число простым, относительно несложно, но если число составное, то отыскать его простые множители часто намного труднее.

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

В школьной арифметике простые делители используют для поиска наибольшего общего делителя двух чисел. К примеру, чтобы найти наибольший общий делитель чисел 135 и 630, мы раскладываем их на простые множители:

135= З³ х 5; 630 = 2 х З² х 5 х 7.

Затем берем все простые числа, которые присутствуют в обоих разложениях, в наибольшей общей степени; получаем 32 х 5. Перемножаем, получаем 45. Это и есть наибольший общий делитель. Из этой процедуры создается впечатление, что без разложения на простые множители невозможно найти наибольший общий делитель. На самом деле с точки зрения логики все наоборот. Предложение 2 Книги VII «Начал» представляет метод поиска наибольшего общего делителя двух натуральных чисел без разложения их на простые множители. Метод состоит в последовательном вычитании меньшего числа из большего, а затем остатка из меньшего числа и т. д. до тех пор, пока есть остаток. Для тех же чисел 135 и 630 — это достаточно типичный случай для небольших чисел — процесс выглядит так. Вычитаем 135 из 630 столько раз, сколько сможем:

630 -135 = 495;

495 -135 = 360;

360-135 = 225;

225 — 135 = 90.

Поскольку 90 < 135, переходим к той же процедуре с участием чисел 90 и 135:

135-90 = 45.

Поскольку 45 < 90, продолжаем то же с числами 45 и 90:

90-45 = 45;

45 — 45 = 0.

Таким образом, наибольший общий делитель чисел 135 и 630 равен 45.

Эта процедура работает потому, что на каждой стадии происходит замена первоначальной пары чисел более простой парой (одно из чисел уменьшается), которая тем не менее имеет тот же наибольший общий делитель. В конце концов, одно из чисел делится на второе нацело, без остатка, и процесс поиска на этом завершается. В наше время подробное описание вычислительного метода, при помощи которого можно гаран­тированно найти ответ той или иной задачи, называют алгоритмом. Поэтому и процедура из «Начал» Евклида известна сегодня как евклидов алгоритм. Логически эта процедура первична по отношению к процедуре разложения на простые множители. В самом деле, Евклид использует ее для доказательства основных свойств простых делителей. В современных университетских курсах математики алгоритм Евклида используется с той же целью.

Число 1 не простое!

Проясню один небольшой, но важный момент: исключительный статус числа 1. Согласно определению, оно простое: если мы попытаемся разбить его на множители, максимум, что мы получим, будет 1 = 1 x 1, где нет меньших чисел. Однако позже, с развитием теории, такая интерпретация вызывает проблемы, поэтому в последние век-два математики добавили в определение простого числа дополнительное ограничение. Число 1 настолько отличается от всех остальных чисел, что его следует рассматривать как исключение, — это не простое число, но и не составное. Это третья разновидность числа — единица. Одна из причин, по которым мы называем 1 особым случаем, а не относим ее к настоящим простым числам, заключается в том, что если мы согласимся с простотой единицы, то единственность набора множителей нарушится. Вообще-то 1 x 1 = 1 – уже нарушение, а уж 1 х 1 х 1 х 1 х 1 х 1 х 1 х 1 = 1 ни в какие ворота не лезет. Можно было бы изменить определение единственности и сказать «единственный, без учета дополнительных единичных множителей», но это был бы всего лишь другой способ признать, что 1 — число особое.

Много позже, в Предложении 20 Книги IX, Евклид доказывает еще один ключевой факт: «Простых чисел существует больше, чем их насчитывается в любом множестве простых чисел». Иными словами, множество простых чисел бесконечно. Это чудесная теорема и изящное доказательство, но ее появление вызвало множество проблем. Если простые числа уходят в бесконечность, но, судя по всему, расположены без всякой системы, то как можно сказать, на что они похожи?

Теория чисел — один из самых глубоких и сложных разделов математики. В 1801 г. Гаусс, ведущий специалист того времени по теории чисел (а также, по мнению некоторых ученых, один из ведущих математиков всех времен, а может быть, и величайший из них), написал продвинутый учебник по этой теории — «Арифметические исследования» (Disquisitiones Arithmeticae). В нем среди множества сложных тем Гаусс указал, что не следует терять из виду два весьма фундаментальных вопроса: «Известно, что задача отличения простых чисел от составных и разложения последних на простые множители является одной из важнейших и полезнейших в арифметике».

В школе, как правило, учат ровно одному способу поиска простых делителей числа. Заключается он в том, чтобы пробовать по очереди все потенциальные делители, пока не найдется такой, на который число разделится нацело. Если вы не нашли ни одного делителя к тому моменту, как добрались до корня квадратного из первоначального числа — точнее, до наибольшего целого числа, меньшего или равного этому корню, — то число это простое. В противном случае вы найдете множитель, разделите на него и продолжите с новым числом с того же места. Эффективнее всего пробовать только простые делители, но для этого необходим список простых чисел. Поиск останавливается на корне квадратном из числа, потому что наименьший делитель любого составного числа не превосходит корень квадратный из этого числа. Однако для больших чисел эта процедура безнадежно неэффективна. К примеру, если взять число

1080 813 321843 836 712 253,

то на простые множители оно раскладывается следующим образом: 13929010429 х 77594408257,

и, чтобы добраться до меньшего из двух множителей, вам придется опробовать каждое из первых 624401249 простых чисел. Конечно, при помощи компьютера это несложно сделать, но если взять для начала число из 100 цифр, которое — так уж случилось — раскладывается на два множителя по 50 цифр в каждом, то систематический перебор последовательных простых чисел продлится до конца Вселенной и вряд ли успеет дать результат.

Нет, вообще-то современные компьютеры, как правило, умеют раскладывать числа из 100 цифр на простые множители. Однако если я попрошу компьютер разложить на множители число 10¹⁹⁹ + 1, в котором 200 цифр, то жужжать он будет долго, но результата так и не выдаст. Хотя, конечно, даже разложение числа из 100 цифр производит сильное впечатление. В чем тут секрет? В более эффективном по сравнению с последовательным перебором потенциальных простых делителей алгоритме поиска.

Мы сегодня знаем о первой из названных Гауссом задач (проверка числа на простоту) гораздо больше, чем знал он сам, и гораздо меньше, чем хотелось бы, о второй (разложение на простые множители).

Как проверить число на простоту?

Здравый смысл говорит о том, что проверка на простоту намного проще разложения на простые множители. Как правило, это удивляет нематематиков, — ведь в школе учат проверять число на простоту тем же методом, что и искать его простые множители: перебором всех возможных делителей. Но, оказывается, существуют хитрые способы доказать простоту числа и без этого. Эти же методы позволяют доказать, что число составное, без нахождения каких бы то ни было его делителей. Достаточно показать, что это число не проходит тест на простоту.

Прапрадедушкой всех современных тестов на простоту может считаться теорема Ферма (чтобы не путать со знаменитой Великой теоремой, ее иногда называют Малой теоремой Ферма). Эта теорема основана на модулярной арифметике, которую иногда называют еще «часовой арифметикой», поскольку числа в ней спирально накладываются друг на друга, как время на циферблате часов. Выберем число — для 12-часовых аналоговых часов это число 12 — и назовем его модулем. Теперь в любых арифметических вычислениях с неотрицательными целыми числами мы догово­римся заменять любое число, кратное 12, нулем. К примеру, 5 х 5 = 25, но 24 — это дважды 12, поэтому вычтем из результата 24. Получим 5 х 5 = 1 по модулю 12. Модулярная арифметика очень красива, поскольку почти все обычные арифметические законы в ней тоже работают. Основная разница заключается в том, что мы не всегда можем разделить одно число на другое, даже если это не нуль. Модулярная арифметика полезна также тем, что обеспечивает удобный и аккуратный способ разбираться с вопросами делимости: какие числа делятся на те или иные модули без остатка и чему равен остаток, если это не так. Модулярную арифметику предложил Гаусс в «Арифметических исследованиях», и сегодня она широко используется не только в математике, но и в информатике, физике, инженерном деле.

Малая теорема Ферма утверждает, что если взять простой модуль р и любое число а, не кратное р, то степень (р – 1) числа а будет равна 1 по модулю р. Пусть, к примеру, р = 17 и а = 3. Тогда теорема предсказывает, что остаток от деления 3¹⁶ на 17 будет равен 1. Проверим:

3¹⁶ = 43046721 = 2532160 х 17 + 1.

Ни один человек, находящийся в своем уме, не захочет проводить подобные расчеты для, скажем, 100-значных простых чисел. К счастью, существует хитрый и быстрый способ сделать это. Смысл в том, что ответ не равен единице, если модуль, с которого мы начали, является составным числом. Так что тео­рема Ферма — надежная основа для эффективного теста, который обеспечивает необходимое условие простоты числа.

К несчастью, одного этого теста недостаточно. Известно, что его проходят и многие составные числа, известные как чис­ла Кармайкла. Самое маленькое из них 561, и в 2003 г. Ред Элфорд, Эндрю Гранвиль и Карл Померане доказали, к всеобщему изумлению, что таких чисел бесконечно много. Изумление математического сообщества вызвал тот факт, что авторам удалось найти доказательство; сам по себе результат особого удивления не вызвал. Фактически было доказано, что для каждого числа х существует по крайней мере х^2/7 чисел Кармайкла, меньших или равных х, если х достаточно велико.

Однако более сложные варианты теоремы Ферма действительно можно превратить в тесты на простоту, такие как опубликованный в 1976 г. Гэри Миллером. К несчастью, доказательство достоверности теста Миллера опирается на одну из нерешенных великих математических задач — обобщенную гипотезу Римана. В 1980 г. Майкл Рабин превратил тест Миллера в вероятностный, т.е. такой, который может иногда давать неверный ответ. Исключения, если они существуют, встречаются очень редко, но тем не менее доказать, что их нет, невозможно.

Наиболее эффективным детерминированным (т.е. дающим гарантированный результат) тестом на сегодняшний день является тест Адлемана-Померанса-Румели, названный в честь своих создателей — Леонарда Адлемана, Карла Померанса и Роберта Румели. В нем используются концепции теории чисел, куда более сложные, чем теорема Ферма, но примерно того же характера.

(продолжение следует)

Литература
И.М. Виноградов «Основы теории чисел»;
Иэн Стюард «Величайшие математические задачи».