Функция Кармайкла — теоретико-числовая функция, обозначаемая
, равная наименьшему показателю
такому, что

для всех целых
, взаимно простых с модулем
. Говоря языком теории групп,
— это экспонента мультипликативной группы вычетов по модулю
.
Приведем таблицу первых 36 значений функции
последовательность A002322 в OEIS в сравнении со значениями функции Эйлера
. (жирным выделены отличающиеся значения)
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 |
---|
 | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 2 | 6 | 4 | 10 | 2 | 12 | 6 | 4 | 4 | 16 | 6 | 18 | 4 | 6 | 10 | 22 | 2 | 20 | 12 | 18 | 6 | 28 | 4 | 30 | 8 | 10 | 16 | 12 | 6 |
---|
 | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 | 12 | 6 | 8 | 8 | 16 | 6 | 18 | 8 | 12 | 10 | 22 | 8 | 20 | 12 | 18 | 12 | 28 | 8 | 30 | 16 | 20 | 16 | 24 | 12 |
---|
Пример
1,3,5,7 — все числа, меньшие 8 и взаимно простые с ним,
, значит функция Кармайкла
равна 2. Функция Эйлера
равна 4, поскольку в списке 1,3,5,7 ровно 4 числа.
Теорема Кармайкла
Функция Кармайкла
от степеней нечётных простых, а также для чисел 2 и 4, равна функции Эйлера
; для степеней двойки, больших 4, она равна половине функции Эйлера:

Функция Эйлера для степеней простых есть

По основной теореме арифметики любое
может быть представлено как

где
— простые числа, а все
.
В общем случае,
— это наименьшее общее кратное
всех точных степеней простых, входящих в разложение
на множители:
![{\displaystyle \lambda (n)=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{s}^{a_{s}})].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99a12e2f1cef0c835a47ac956fe318fc8b6980c9)
- Теорема Кармайкла
Если
взаимно просты, то

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

Тогда по методу математической индукции мы получаем, что для всех
.
Для модуля 2 соотношение несколько сильнее:
Если
нечётно, то
.
Тогда
.
Далее, если
, то

Тогда по математической индукции мы получаем, что для всех нечётных
при
верно, что
.
Наконец, если
и
взаимно просто с
, то
и
, значит
и
и тогда
.
Заметим также, что для любых
утверждение нельзя усилить: показатель
— минимальный, для которого
. Это легко доказывается от противного.
Действительно, пусть есть простое
такое, что для всех
. Поскольку
, то
делит какое-то
, то есть для всех
. Однако это противоречит тому факту, что группа
циклична при
, а при
— противоречит тому факту, что группа
имеет экспоненту
. ■
Связь теорем Кармайкла, Эйлера и Ферма
Поскольку функция Кармайкла
делит функцию Эйлера
(последовательность их частных см. в последовательность A034380 в OEIS), теорема Кармайкла является более сильным результатом, чем классическая теорема Эйлера. Ясно, что теорема Кармайкла связана с теоремой Эйлера, потому что экспонента конечной абелевой группы всегда делит порядок группы. Функции Кармайкла и Эйлера отличаются уже при небольших аргументах:
, но
, они отличаются всегда, когда группа вычетов по модулю
не имеет образующей (см. последовательность A033949).
Малая теорема Ферма — это частный случай теоремы Эйлера, в котором модуль
— это простое число. Теорема Кармайкла для простых модулей дает то же утверждение, поскольку группа вычетов по простому модулю является цикличной, то есть её порядок и экспонента совпадают.
Свойства функции Кармайкла
Делимость

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

В частности, для
свободного от квадратов
(для него
), для всех 

Средние и типичные значения
Для любого
и константы
:
[1][2].
Здесь

Для любого
и для всех
, за исключением
чисел верно, что:

где
— это постоянная[2][3],

Оценки снизу
Для достаточно больших
и для любых
существует как минимум
![{\displaystyle Ne^{-0.69{\sqrt[{3}]{\Delta \ln \Delta }}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/488adb2234084f7f389e5277af2e404fd59b814f)
натуральных
таких, что
[4].
Для любой последовательности натуральных чисел
, любой константы
и для достаточно большого
:
[5][6].
Небольшие значения
Для постоянного
и достаточно большого положительного
существует целое
такое, что
[6]. Более того, такое
имеет вид

при некотором
, свободном от квадратов[5].
Множество значений функции Кармайкла
Множество значений функции Кармайкла, не превосходящих
, имеет мощность

где
[7]
См. также
Примечания
- ↑ Theorem 3 in Erdos (1991)
- ↑ 1 2 Sandor & Crstici (2004) p.194
- ↑ Theorem 2 in Erdos (1991)
- ↑ Theorem 5 in Friedlander (2001)
- ↑ 1 2 Theorem 1 in Erdos 1991
- ↑ 1 2 Sandor & Crstici (2004) p.193
- ↑ Ford, Kevin; Luca, Florian; Pomerance, Carl (27 August 2014). "The image of Carmichael's ?-function". arXiv:1408.6506 [math.NT].
Литература
- Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. (гл. 11 п.2)
- Erdos, Paul[англ.]; Pomerance, Carl[англ.]; Schmutz, Eric. Carmichael's lambda function (неопр.) // Acta Arithmetica[англ.]. — 1991. — Т. 58. — С. 363—385. — ISSN 0065-1036.
- Friedlander, John B.[англ.]; Pomerance, Carl; Shparlinski, Igor E. Period of the power generator and small values of the Carmichael function (англ.) // Mathematics of Computation[англ.] : journal. — 2001. — Vol. 70. — P. 1591—1605, 1803—1806. — ISSN 0025-5718. — doi:10.1090/s0025-5718-00-01282-5.
- Sandor, Jozsef; Crstici, Borislav. Handbook of number theory II (неопр.). — Dordrecht: Kluwer Academic, 2004. — С. 32—36,193—195. — ISBN 1-4020-2546-7.
- Carmichael, R. D. The Theory of Numbers (неопр.). — Nabu Press. — ISBN 1144400341.