§ 7.2. Числа Кармайкла

Как мы показали в конце последнего параграфа, составное число не является псевдопростым по основанию если числа и имеют общий нетривиальный делитель. К сожалению, эта информация не очень полезна. Практически, чтобы ограничить объем вычислений разумными рамками, мы выделяем несколько оснований среди небольших простых чисел. И если наименьший делитель числа очень большой, то все выбранные основания будут взаимно просты с Поэтому вопрос, который нам стоило бы задать, нужно нацелить на усовершенствование метода, приведенного в конце предыдущего параграфа. А именно, может ли составное нечетное число быть псевдопростым по всем взаимно простым с ним основаниям Забегая вперед, скажем, что ответ: «да».

Заметим, что если число взаимно просто с то сравнение равносильно Это позволяет поставить вопрос чуть более строго: существует ли такое нечетное натуральное которое, будучи составным, удовлетворяет сравнениям для всех целых b? Одно из преимуществ такой формулировки вопроса

заключается в отсутствии необходимости каких-либо предварительных предположений относительно Ь. Первым привел пример таких чисел математик Р. Д. Кармайкл (Carmichael) в своей работе, опубликованной в 1912 году Поэтому они и называются числами Кармайкла.

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

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

Самое подходящее время вернуться к доске и мелу (т.е. теоретическим изысканиям).

Попытаемся найти обходной путь для доказательства того, что 561 — число Кармайкла. Прежде всего заметим, что оно довольно легко раскладывается на простые множители:

Теперь мы хотим проверить сравнение

для некоторого целого Наша стратегия состоит в демонстрации делимости разности на 3, 11 и 17. Так как это различные простые числа, то лемма из главы 3 говорит нам, что тогда их произведение тоже должно делить Но упомянутое произведение равно 561, так что (2.1) этим будет доказано.

Чтобы сделать нашу стратегию рабочей, нужно исхитриться доказать, что делится на каждый простой множитель числа 561. В этом нам поможет теорема Ферма. Мы приведем подробное доказательство делимости разности на 17, оставив случаи делимости на 3 и на 11 в качестве полезных и необременительных упражнений. Итак, мы хотим доказать, что 17 делит разность или, на языке сравнений:

Необходимо рассмотреть два случая.

1) Число 17 делит В этой ситуации обе части уравнения (2.2) сравнимы с 0 по модулю 17, т.е. сравнение справедливо.

2) Число 17 не делит Тогда теорема Ферма влечет равенство: . Прежде чем применить это наблюдение к сравнению (2.2), нам нужно найти остаток от деления 561 на 16. Но поэтому

Заметим, теорема Ферма так сильно сократила наши вычисления благодаря тому, что остаток от деления 561 на 16 оказался равным 1. Удачно, что остатки от деления 561 на и на тоже равны 1. Так что вычисления, которые Вам предстоит сделать для 3 и 11 — дословное повторение проведенных.

Успех нашей стратегии обязан двум свойствам числа 561. Первое: деление 561 на разность каждого из его делителей и единицы дает в остатке 1. Второе: каждый простой делитель

числа 561 входит в его разложение на простые множители с кратностью 1. Что же это: нам очень повезло с выбором примера, или числа Кармайкла встречаются крайне редко? Реальность оказывается еще более удивительной. Существует бесконечно много чисел Кармайкла, и все они обладают свойствами, столь облегчившими наши вычисления с 561. Характеристика чисел Кармайкла, вытекающая из этого наблюдения, впервые была дана А. Корселтом (A. Korselt) за пятнадцать лет до публикации работы Кармайкла на эту тему. Однако, Корселт не привел никаких новых примеров чисел, которые удовлетворяли бы описанным им свойствам.

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

Покажем для начала, что если число удовлетворяет условиям (1) и (2) теоремы, то оно является числом Кармайкла. Для этого мы применим стратегию, разработанную в предыдущих вычислениях с числом 561. Предположим, что простой делитель числа Покажем, что

Если b делится на то обе части в (2.3) сравнимы с нулем по модулю и доказывать нечего. Предположим теперь, что не делит Как следует из теоремы Ферма, Прежде чем применить это соображение к (2.3), мы должны найти остаток от деления на Но делит согласно условию (2) теоремы, т.е. для некоторого целого и

Значит

где второе сравнение следует из теоремы Ферма. Суммируя все вышесказанное, получаем, что если простой делитель числа то для любого целого

Ввиду условия (1) теоремы, где попарно различные простые числа. Мы уже видели, что делится на каждое из этих чисел, а поскольку все они различны, то, учитывая лемму § 3.6, можно сделать вывод: делится на их произведение Иначе говоря, Поскольку вычисления справедливы для любого целого то является числом Кармайкла.

Теперь следует показать, что всякое число Кармайкла удовлетворяет условиям (1) и (2) теоремы. Сделаем это методом «от противного». Сначала, предположив, что число Кармайкла, получим, что делимость на приводит к противоречию. Этим мы докажем, что числа Кармайкла удовлетворяют условию (1) теоремы.

Так как число Кармайкла, противоречие получится, если мы найдем целое для которого Положим Тогда

Но не делит поэтому не может делить Иначе говоря, Это противоречит предположению о том, что число Кармайкла.

Для завершения доказательства нам осталось показать, что числа Кармайкла удовлетворяют условию (2) теоремы. Однако для этого необходима теорема о примитивных корнях, которая будет доказана только в § 11.3.

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

наименьшим числом Кармайкла с 20 простыми делителями. Его разложение на множители выглядит следующим образом:

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

В своей работе 1912 года Кармайкл выписал 15 чисел, названных его именем, а затем добавил: «этот список можно продолжать бесконечно». То есть он имел в виду, что существует бесконечно много чисел Кармайкла. Однако скоро стало ясно, что доказательство этого утверждения — очень трудная проблема. Причина высокой сложности задачи в том, что такие числа достаточно редко встречаются. Например, между 1 и 109 лежит только 646 чисел Кармайкла, в то время как простых — 50847534. Проблема, наконец, была решена Альфордом (Alford), Гранвиллем (Granville) и Померанцем в 1994 году. Они показали, что на самом деле существует бесконечно много чисел Кармайкла. Побочный продукт этого результата имеет отношение к тестированию простоты и будет обсуждаться в § 7.4.