§ 11.2. Еще один тест на простоту

Простой пример, приведенный ниже, проливает свет на одну из главных трудностей, с которой мы сталкиваемся, применяя тест Люка. Предположим, что мы хотим доказать простоту числа 41 с помощью этого теста. Сначала раскладываем на множители: Затем погружаемся в поиски числа заключенного между 2 и 40, которое удовлетворяло бы следующим условиям:

Начиная проверять условия для вскоре находим, что . Взяв другого кандидата, мы, затаив дыхание, узнаем, что , но уже следующее сравнение, , подрезает нам крылья. Еще более расстраиваемся, обнаружив, что . Таким образом, разные кандидаты удовлетворяют требуемым сравнениям при разных простых делителях числа Неприятность в том, что необходим один кандидат, удовлетворяющий

всем сравнениям. В случае наименьшее такое число равно 7.

В 1975 году Брилхарт (Brilhart), Лемер и Селфридж (Selfridge) поставили себе целью так усовершенствовать тест Люка, чтобы для разных простых делителей числа можно было находить вычеты различных чисел Это намного бы упростило применение теста. Результат их усилий сформулирован ниже.

Тест на простоту. Пусть нечетное натуральное число, причем

где простые числа. Если для каждого существует такое целое число что

то простое.

Отметим, что числа не обязательно должны быть различными.

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

где

С другой стороны, нам известно, что Значит, не делится на Но

Сравнивая разложения чисел учитывая при этом, что не делит мы убеждаемся в равенстве Другими словами, делит

Напомним, что через мы обозначили порядок элемента группы По теореме Лагранжа он должен делить порядок группы А так как делитель то делит и

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

тоже делит Учитывая неравенство замечаем, что такое возможно, только если Итак, простое число.

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

(1) проверяем, делится ли на какое-нибудь простое число, не превосходящее 5000;

(2) если не делится ни на одно из них, применяем к нему тест Миллера, используя в качестве оснований первые 20 простых чисел;

(3) если тест Миллера по всем этим основаниям дает неопределенный ответ, то подвергаем тесту на простоту.