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

Мы видели, что числа Кармайкла можно определить в терминах разложения на простые множители. Это утверждает теорема Корселта, неполное доказательство которой мы привели в § 7.2. Поскольку для окончания доказательства требовалась теорема о примитивных корнях, теперь мы в состоянии завершить доказательство. Напомним формулировку теоремы.

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

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

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

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