Число Кармайкла

Число Кармайкла — это составное натуральное число \(n\), которое удовлетворяет сравнению \(a^{n} \equiv a \pmod{n}\) для всех целых чисел \(a\), взаимно простых с \(n\). Другими словами, для любого целого \(a\), такого что \(\gcd(a, n) = 1\), выполняется \(a^{n-1} \equiv 1 \pmod{n}\). Числа Кармайкла являются подмножеством псевдопростых чисел Ферма и представляют собой «обманщики» малой теоремы Ферма: для составного числа \(n\) сравнение, которое должно быть верным только для простых чисел, выполняется для всех оснований, взаимно простых с \(n\).

История

Понятие чисел Кармайкла было введено американским математиком Робертом Кармайклом (Robert Daniel Carmichael) в 1910 году. В своей работе «Note on a new number theory function» (1910) он описал первые три таких числа: 561, 1105 и 1729. Кармайкл искал составные числа, которые «ведут себя» как простые в тесте Ферма, и обнаружил, что для них сравнение \(a^{n-1} \equiv 1 \pmod{n}\) выполняется для всех \(a\), взаимно простых с \(n\). До этого считалось, что такие числа крайне редки, но Кармайкл показал их существование и дал метод построения.

В 1939 году Джон Черч (John Chernick) доказал, что если три числа \(6k+1\), \(12k+1\) и \(18k+1\) являются простыми, то их произведение даёт число Кармайкла. Это дало бесконечное семейство таких чисел, хотя их плотность остаётся низкой. В 1994 году Ричард Гай (Richard Guy) и Эндрю Гранелл (Andrew Granville) показали, что количество чисел Кармайкла до \(x\) растёт медленнее, чем \(x^{1/3}\), но точная асимптотика неизвестна.

Определение и свойства

Формальное определение

Натуральное составное число \(n\) называется числом Кармайкла, если для всех целых \(a\), таких что \(\gcd(a, n) = 1\), выполняется: \[ a^{n-1} \equiv 1 \pmod{n}. \] Эквивалентно, \(n\) является псевдопростым числом Ферма по всем основаниям, взаимно простым с \(n\).

Критерий Корсельта

В 1899 году (до работы Кармайкла) Альвин Корсельт (Alwin Korselt) сформулировал необходимое и достаточное условие для того, чтобы составное число \(n\) было числом Кармайкла. Критерий Корсельта гласит:

Число \(n\) является числом Кармайкла тогда и только тогда, когда:

1. \(n\) нечётно (так как любое чётное составное число, большее 2, не может быть числом Кармайкла, поскольку для \(a = n-1\) сравнение не выполняется).
2. \(n\) свободно от квадратов (то есть не делится на квадрат простого числа).
3. Для каждого простого делителя \(p\) числа \(n\) выполняется \(p-1 \mid n-1\).

Этот критерий позволяет эффективно проверять, является ли число числом Кармайкла, и строить такие числа.

Примеры

• 561 — наименьшее число Кармайкла. Его разложение: \(561 = 3 \times 11 \times 17\). Проверка: \(3-1=2 \mid 560\), \(11-1=10 \mid 560\), \(17-1=16 \mid 560\).
• 1105 = \(5 \times 13 \times 17\): \(5-1=4 \mid 1104\), \(13-1=12 \mid 1104\), \(17-1=16 \mid 1104\).
• 1729 = \(7 \times 13 \times 19\) (известное как число Рамануджана — Харди): \(7-1=6 \mid 1728\), \(13-1=12 \mid 1728\), \(19-1=18 \mid 1728\).
• 2465 = \(5 \times 17 \times 29\).
• 2821 = \(7 \times 13 \times 31\).

Классификация и виды

Числа Кармайкла с тремя простыми множителями

Наиболее распространённый тип — числа вида \(p \times q \times r\), где \(p, q, r\) — различные простые числа, удовлетворяющие условию Корсельта. Черч показал, что для любого \(k\) такого, что \(6k+1\), \(12k+1\) и \(18k+1\) — простые, их произведение даёт число Кармайкла. Пример: \(k=1\) даёт \(7 \times 13 \times 19 = 1729\).

Числа Кармайкла с четырьмя и более простыми множителями

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

• 41041 = \(7 \times 11 \times 13 \times 41\) (четыре множителя).
• 62745 = \(3 \times 5 \times 7 \times 13 \times 23\) (пять множителей).
• 321197185 = \(5 \times 19 \times 23 \times 29 \times 37 \times 43\) (шесть множителей).

Числа Кармайкла с одним простым множителем?

Не существует чисел Кармайкла, являющихся степенью простого числа (например, \(p^k\) для \(k>1\)), так как они не свободны от квадратов. Также не существует чисел Кармайкла, являющихся произведением двух простых чисел, так как для \(n = p \times q\) условие \(p-1 \mid n-1\) и \(q-1 \mid n-1\) приводит к противоречию (кроме случая, когда \(p\) и \(q\) — простые числа Ферма, но это не даёт равенства). Таким образом, минимальное количество простых множителей — три.

Распределение и плотность

Числа Кармайкла встречаются редко. По состоянию на 2024 год известно:

• До \(10^3\): 1 число (561).
• До \(10^4\): 7 чисел.
• До \(10^5\): 16 чисел.
• До \(10^6\): 43 числа.
• До \(10^7\): 105 чисел.
• До \(10^8\): 255 чисел.
• До \(10^9\): 646 чисел.
• До \(10^{10}\): 1547 чисел.
• До \(10^{12}\): около 20 000 чисел.
• До \(10^{15}\): около 100 000 чисел.

Асимптотическая плотность чисел Кармайкла относительно всех натуральных чисел стремится к нулю. В 1994 году Ричард Гай и Эндрю Гранелл доказали, что количество \(C(x)\) чисел Кармайкла, не превосходящих \(x\), удовлетворяет неравенству: \[ C(x) < x^{1/3} \cdot \exp\left( O\left( \frac{\log x}{\log \log x} \right) \right). \] Более точная оценка: \(C(x) \approx x^{1/3} \cdot (\log x)^{O(1)}\), но точная константа неизвестна.

Применение и значение

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

Числа Кармайкла представляют интерес в криптографии, особенно в алгоритмах, основанных на малой теореме Ферма, таких как тест простоты Ферма. Если использовать тест Ферма для проверки простоты, числа Кармайкла будут ошибочно приняты за простые, что может привести к уязвимостям в системах шифрования (например, RSA, где требуется генерация больших простых чисел). Поэтому в современных криптосистемах применяют более надёжные тесты, такие как тест Миллера — Рабина или тест Соловея — Штрассена, которые не подвержены обману со стороны чисел Кармайкла.

Теория чисел

Числа Кармайкла являются важным объектом в теории чисел, иллюстрируя ограничения малой теоремы Ферма. Они связаны с понятием псевдопростых чисел, а также с гипотезой о бесконечности чисел Кармайкла (доказана в 1994 году Ричардом Гаем и Эндрю Гранеллом). Изучение их распределения помогает понять структуру мультипликативных групп по модулю составных чисел.

Образовательное значение

Числа Кармайкла часто используются в учебных курсах по теории чисел и криптографии для демонстрации того, что не все числа, удовлетворяющие тесту Ферма, являются простыми. Они также служат примером «обманщиков» в математике.

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

• Число 1729 (число Рамануджана — Харди) является числом Кармайкла. Это число известно благодаря анекдоту: когда Харди навестил Рамануджана в больнице, он сказал, что приехал на такси с номером 1729, которое «скучное». Рамануджан ответил, что это число интересно, так как оно наименьшее, представимое в виде суммы двух кубов двумя различными способами (\(1^3 + 12^3 = 9^3 + 10^3\)). Позже выяснилось, что оно также является числом Кармайкла.
• Наименьшее число Кармайкла с четырьмя простыми множителями — 41041.
• Наименьшее число Кармайкла с пятью простыми множителями — 62745.
• Числа Кармайкла не могут быть чётными, так как для чётного \(n\) и \(a = n-1\) (нечётного) сравнение \(a^{n-1} \equiv 1 \pmod{n}\) не выполняется (так как \(n-1\) нечётно, а \(n\) делится на 2, то \(a^{n-1} \equiv 1 \pmod{2}\) неверно).
• Все числа Кармайкла нечётны и свободны от квадратов.
• Гипотеза о бесконечности была доказана в 1994 году, но до сих пор не найдено эффективного способа генерации всех чисел Кармайкла.

Источники

• Carmichael, R. D. (1910). «Note on a new number theory function». Bulletin of the American Mathematical Society.
• Korselt, A. (1899). «Problème chinois». L’Intermédiaire des Mathématiciens.
• Chernick, J. (1939). «On Fermat’s simple theorem». Bulletin of the American Mathematical Society.
• Guy, R. K., & Granville, A. (1994). «Carmichael numbers». Mathematics of Computation.
• Ribenboim, P. (1996). The New Book of Prime Number Records. Springer.
• Crandall, R., & Pomerance, C. (2005). Prime Numbers: A Computational Perspective. Springer.