Теорема Кармайкла

Теорема Кармайкла — это утверждение в теории чисел, относящееся к свойствам функции Эйлера и модулярной арифметике. В наиболее известной формулировке она описывает структуру мультипликативной группы целых чисел по модулю составного числа, а также обобщает малую теорему Ферма. Теорема названа в честь американского математика Роберта Кармайкла (Robert Daniel Carmichael), который опубликовал её в 1912 году.

Формулировка

Пусть \( n \) — натуральное число. Обозначим через \( \lambda(n) \) функцию Кармайкла, которая определяется как наименьшее положительное целое число \( m \) такое, что для всех целых \( a \), взаимно простых с \( n \), выполняется сравнение:

\[ a^m \equiv 1 \pmod{n} \]

Теорема Кармайкла утверждает, что такое число \( m \) существует и может быть вычислено по следующему правилу:

• Если \( n = 2 \), то \( \lambda(2) = 1 \).
• Если \( n = 4 \), то \( \lambda(4) = 2 \).
• Если \( n = 2^k \) при \( k \ge 3 \), то \( \lambda(2^k) = 2^{k-2} \).
• Если \( n = p^k \), где \( p \) — нечётное простое число, то \( \lambda(p^k) = \varphi(p^k) = p^{k-1}(p-1) \), где \( \varphi \) — функция Эйлера.
• Если \( n = p_1^{k_1} p_2^{k_2} \dots p_r^{k_r} \) — разложение на простые множители, то \( \lambda(n) \) равно наименьшему общему кратному (НОК) значений \( \lambda(p_i^{k_i}) \):

\[ \lambda(n) = \operatorname{lcm}\bigl( \lambda(p_1^{k_1}), \lambda(p_2^{k_2}), \dots, \lambda(p_r^{k_r}) \bigr) \]

Таким образом, теорема даёт явную формулу для вычисления \( \lambda(n) \), которая всегда делит функцию Эйлера \( \varphi(n) \), но в общем случае меньше её.

Связь с малой теоремой Ферма

Малая теорема Ферма утверждает, что для простого числа \( p \) и любого целого \( a \), не кратного \( p \), выполняется \( a^{p-1} \equiv 1 \pmod{p} \). Теорема Кармайкла обобщает этот результат на составные модули: для любого \( n \) и любого \( a \), взаимно простого с \( n \), верно \( a^{\lambda(n)} \equiv 1 \pmod{n} \). При этом \( \lambda(n) \) — наименьший возможный показатель, обладающий таким свойством для всех \( a \).

История

Роберт Кармайкл впервые опубликовал свою теорему в 1912 году в статье «On the numerical factors of the arithmetic forms \( \alpha^n \pm \beta^n \)» в журнале Annals of Mathematics. Он исследовал свойства чисел, которые позже были названы числами Кармайкла — составными числами, для которых \( \lambda(n) \) делит \( n-1 \). Теорема стала важным инструментом в теории чисел и криптографии.

Примеры вычисления

1. Для \( n = 12 \): Разложение: \( 12 = 2^2 \cdot 3 \). \( \lambda(2^2) = \lambda(4) = 2 \), \( \lambda(3) = \varphi(3) = 2 \). НОК(2, 2) = 2. Следовательно, \( \lambda(12) = 2 \). Проверка: для любого \( a \), взаимно простого с 12 (т.е. \( a = 1, 5, 7, 11 \)), \( a^2 \equiv 1 \pmod{12} \).

1. Для \( n = 15 \): \( 15 = 3 \cdot 5 \). \( \lambda(3) = 2 \), \( \lambda(5) = 4 \). НОК(2, 4) = 4. Значит, \( \lambda(15) = 4 \). Действительно, \( 2^4 = 16 \equiv 1 \pmod{15} \), \( 7^4 = 2401 \equiv 1 \pmod{15} \).

1. Для \( n = 8 \): \( 8 = 2^3 \). По правилу для \( k \ge 3 \), \( \lambda(8) = 2^{3-2} = 2 \). Проверка: \( 3^2 = 9 \equiv 1 \pmod{8} \), \( 5^2 = 25 \equiv 1 \pmod{8} \), \( 7^2 = 49 \equiv 1 \pmod{8} \).

Свойства функции Кармайкла

• Мультипликативность: Функция \( \lambda(n) \) не является мультипликативной в обычном смысле, но для взаимно простых \( m \) и \( n \) выполняется \( \lambda(mn) = \operatorname{lcm}(\lambda(m), \lambda(n)) \).
• Делимость на \( \lambda(n) \): Для любого \( a \), взаимно простого с \( n \), порядок элемента \( a \) в мультипликативной группе \( (\mathbb{Z}/n\mathbb{Z})^\times \) делит \( \lambda(n) \).
• Сравнение с \( \varphi(n) \): \( \lambda(n) \) всегда делит \( \varphi(n) \). Равенство достигается только для \( n = 1, 2, 4, p^k \) и \( 2p^k \), где \( p \) — нечётное простое, а \( k \ge 1 \).
• Числа Кармайкла: Составное число \( n \) называется числом Кармайкла, если для всех \( a \), взаимно простых с \( n \), выполняется \( a^{n-1} \equiv 1 \pmod{n} \). Это эквивалентно тому, что \( \lambda(n) \) делит \( n-1 \). Наименьшее число Кармайкла — 561.

Применение

Криптография

Теорема Кармайкла используется в криптосистеме RSA. В RSA модуль \( n = pq \) (произведение двух простых чисел). Функция Эйлера \( \varphi(n) = (p-1)(q-1) \) используется для вычисления секретного ключа. Однако \( \lambda(n) = \operatorname{lcm}(p-1, q-1) \) также может быть использована, и она даёт наименьший возможный показатель, что иногда упрощает вычисления. В современных реализациях RSA часто применяют \( \lambda(n) \) вместо \( \varphi(n) \).

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

Теорема лежит в основе теста простоты Миллера — Рабина, который использует свойства показателей по модулю. Для составных чисел, не являющихся числами Кармайкла, тест позволяет быстро выявить составную природу.

Теория чисел

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

Интересные факты

• Числа Кармайкла, названные в честь того же математика, являются «обманщиками» для малой теоремы Ферма: они ведут себя как простые в тесте Ферма, но на самом деле составные. Их существование показывает, что обратная малая теорема Ферма неверна.
• Теорема Кармайкла тесно связана с понятием первообразного корня. Для модуля \( n \) первообразный корень существует тогда и только тогда, когда \( \lambda(n) = \varphi(n) \), то есть для \( n = 1, 2, 4, p^k, 2p^k \).
• В 1994 году американский математик Джон Фридлендер и его коллеги доказали, что чисел Кармайкла бесконечно много, но они встречаются редко.

Источники

• Carmichael, R. D. (1912). «On the numerical factors of the arithmetic forms \( \alpha^n \pm \beta^n \)». Annals of Mathematics.
• Hardy, G. H.; Wright, E. M. (2008). An Introduction to the Theory of Numbers. Oxford University Press.
• Коблиц, Н. (2001). Курс теории чисел и криптографии. М.: Наука.
• Rosen, K. H. (2011). Elementary Number Theory and Its Applications. Addison-Wesley.