Глава 7. Псевдопростые числа

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

§ 7.1. Псевдопростые числа

Как утверждает теорема Ферма, для целого числа о, не делящегося на простое имеет место сравнение: Предположим, что нам нужно узнать, является ли данное нечетное число простым. Допустим также, что нам как-нибудь удалось найти целое не делящееся на и удовлетворяющее условию: В этом случае теорема Ферма говорит нам, что не может быть простым. Такое число будем называть свидетелем разложимости Итак, у нас есть метод тестирования числа на наличие нетривиальных делителей, при котором не нужно разлагать число на множители. Трудность применения этого теста заключается в том, что он не будет работать до тех пор, пока мы не найдем свидетеля; а это

требует везения. Но как мы дальше увидим, более вероятно, что такой свидетель будет найден, чем не найден.

Заметим, что для поиска свидетеля нам нет нужды просматривать все целые числа. Действительно, поскольку мы работаем с сравнениями по модулю можно ограничить поиск числами лежащими в интервале Имеет смысл исключить еще 0 (поскольку не должно делиться на и 1 (ибо для всех Более того, из нечетности вытекает сравнение: т.е. сравнение выполнено и для Итак, можно предполагать, что искомый свидетель b удовлетворяет неравенству: Прежде, чем мы будем применять этот тест, сформулируем его в виде теоремы.

Тест на разложимость. Пусть нечетное натуральное число. Если найдется такое целое число что

то разложимое, т.е. составное число.

Напомним, что повторяющиеся единицы определяются формулой

Другими словами, это целые числа, в десятичной записи которых встречаются только 1 (см. упражнение 5 главы 3). Мы уже видели, что составное число для разложимых Однако для простого числа 229 у нас до сих пор не было возможности определить, простое ли или составное. Кроме того, это число состоит из более чем 200 знаков, так что раскладывать его на множители слишком утомительно. Вместо этого применим тест на разложимость с С помощью системы символьных вычислений легко найти вычет по

модулю Он равен

и не сравним с 1 по модулю Так что составное число.

Поскольку нас больше интересуют простые числа, нежели составные, резонно задать вопрос: можно ли использовать теорему Ферма для доказательства простоты чисел? Более точно, предположим, что положительное нечетное целое число, для которого при некотором целом числе удовлетворяющем неравенству ; обязательно ли будет простым числом? Лейбниц, знаменитый философ и математик, полагал, что ответ утвердительный. Он использовал это соображение как тест на простоту, всегда выбирая 2 в качестве для упрощения вычислений.

К сожалению, Лейбниц был неправ. Например, имеет место сравнение и, по Лейбницу, число 341 должно быть простым. Но составное. Числа, дающие ложный «положительный» результат в этом тесте, известны под именем псевдопростых. Выражаясь точнее, нечетное составное натуральное число удовлетворяющее сравнению для некоторого целого b из интервала называется псевдопростым по основанию Следовательно, 341 — псевдопростое по основанию 2.

Несомненно, тест Лейбница все-таки полезен, хотя и не абсолютно точен. Для малых целых, выбранных наугад, тест чаще дает правильный ответ, чем ошибается. Чтобы убедиться в этом, подсчитаем простые и псевдопростые числа по основанию 2, не превышающие какой-нибудь подходящей грани. Например, между 1 и лежит 50847544 простых и только

5597 псевдопростых по основанию 2. Таким образом, число из этого промежутка, выдержавшее тест Лейбница, будет скорее простым, нежели псевдопростым по основанию 2.

Кроме того, мы применяли этот тест только по одному основанию, а если использовать несколько разных оснований, то количество неопределяемых составных чисел значительно уменьшится. Например, , так что 3 свидетельствует о разложимости числа 341. На самом деле, между 1 и 109 находится 1272 псевдопростых по основаниям 2 и 3 и только 685 псевдопростых по основаниям 2, 3 и 5.

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

Какой можно сделать вывод из результатов этого параграфа? Напомним, что наша цель — найти эффективный способ определения, является ли данное конкретное число простым. Если число имеет небольшой делитель, его можно найти с помощью алгоритма деления методом проб из главы 3. Так что на практике тест на разложимость следует применять только в том случае, когда предварительные рассмотрения показали, что данное число не имеет малых делителей. Таким образом, вопрос, заданный выше, имеет небольшой практический интерес. Было бы быстрее найти делитель, чем пытаться проверить, является ли большое число псевдопростым по всем основаниям между Однако, как мы увидим в следующем параграфе, это не конец истории.

Перед тем, как мы к нему перейдем, может быть полезно заметить, что в некоторых книгах количество простых чисел, не превосходящих , считается меньшим, чем приведенное нами. Это не опечатка, поскольку все эти книги приводят одно и то же число. Ошибочная информация о количестве простых обязана своим появлением датскому математику Бертельсену (Bertelsen), который в 1893 году насчитал на 56 простых чисел меньше, чем в действительности. По иронии судьбы, предполагалось, что его вычисления направлены на исправления неточностей в неких таблицах. Вместо этого он допустил ошибку, которую можно найти в книгах, опубликованных до 1993 года.