Функция Кармайкла — теоретико-числовая функция , обозначаемая ${\displaystyle \lambda (n)}$ , равная наименьшему показателю ${\displaystyle m}$ такому, что

${\displaystyle a^{m}\equiv 1{\pmod {n}}}$

для всех целых ${\displaystyle a}$ , взаимно простых с модулем ${\displaystyle n}$ . Говоря языком теории групп, ${\displaystyle \lambda (n)}$ — это экспонента мультипликативной группы вычетов по модулю ${\displaystyle n}$ .

Приведем таблицу первых 36 значений функции ${\displaystyle \lambda (n)}$ последовательность в OEIS в сравнении со значениями функции Эйлера ${\displaystyle \varphi }$ . (жирным выделены отличающиеся значения)

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
${\displaystyle \lambda (n)}$	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
${\displaystyle \varphi (n)}$	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 и взаимно простые с ним, ${\displaystyle 1^{2}\equiv 1{\pmod {8}};\ 3^{2}=9\equiv 1{\pmod {8}};\ 5^{2}=25\equiv 1{\pmod {8}};\ 7^{2}=49\equiv 1{\pmod {8}}}$ , значит функция Кармайкла ${\displaystyle \lambda (8)}$ равна 2. Функция Эйлера ${\displaystyle \varphi (8)}$ равна 4, поскольку в списке 1,3,5,7 ровно 4 числа.

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

Функция Кармайкла ${\displaystyle \lambda (n)}$ от степеней нечётных простых, а также для чисел 2 и 4, равна функции Эйлера ${\displaystyle \varphi (n)}$ ; для степеней двойки, больших 4, она равна половине функции Эйлера:

${\displaystyle \lambda (n)={\begin{cases}{\frac {1}{2}}\varphi (n),&{\text{если }}n=2^{k},k\geqslant 3,{\text{ т.е. }}n=8,16,32,64,128,256,\,\dots \\\;\;\varphi (n),&{\text{если }}n\in \{2,4\}\;{\text{или}}\;n=p^{k},\;p\in \mathbb {P} ,\;p>2,\;{\text{ т.е. }}\;n=2,3^{k},4,5^{k},7^{k},11^{k},13^{k},17^{k},\,\dots \end{cases}}}$

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

${\displaystyle \varphi (p^{k})=p^{k-1}(p-1).\;}$

По основной теореме арифметики любое ${\displaystyle n>1}$ может быть представлено как

${\displaystyle n=p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{s}^{a_{s}}}$

где ${\displaystyle p_{1}<p_{2}<\dots <p_{s}}$ — простые числа , а все ${\displaystyle a_{i}>0}$ .

В общем случае, ${\displaystyle \lambda (n)}$ — это наименьшее общее кратное ${\displaystyle \lambda (p_{i}^{a_{i}})}$ всех точных степеней простых, входящих в разложение ${\displaystyle n}$ на множители:

${\displaystyle \lambda (n)=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{s}^{a_{s}})].}$

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

Если ${\displaystyle a,n}$ взаимно просты, то

${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$

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

Связь теорем Кармайкла, Эйлера и Ферма

Поскольку функция Кармайкла ${\displaystyle \lambda (n)}$ делит функцию Эйлера ${\displaystyle \varphi (n)}$ (последовательность их частных см. в последовательность в OEIS ), теорема Кармайкла является более сильным результатом, чем классическая теорема Эйлера . Ясно, что теорема Кармайкла связана с теоремой Эйлера , потому что экспонента конечной абелевой группы всегда делит порядок группы. Функции Кармайкла и Эйлера отличаются уже при небольших аргументах: ${\displaystyle \lambda (15)=4}$ , но ${\displaystyle \varphi (15)=8}$ , они отличаются всегда, когда группа вычетов по модулю ${\displaystyle n}$ не имеет образующей (см. последовательность ).

Малая теорема Ферма — это частный случай теоремы Эйлера, в котором модуль ${\displaystyle n}$ — это простое число. Теорема Кармайкла для простых модулей дает то же утверждение, поскольку группа вычетов по простому модулю является цикличной , то есть её порядок и экспонента совпадают.

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

Делимость

${\displaystyle a|b\Rightarrow \lambda (a)|\lambda (b)}$

Функция Кармайкла от НОК

Для любых натуральных ${\displaystyle a,b}$ верно, что

${\displaystyle \lambda (\mathrm {lcm} (a,b))=\mathrm {lcm} (\lambda (a),\lambda (b))}$ .

Это сразу получается из определения функции Кармайкла.

Примитивные корни из единицы

Если ${\displaystyle a,n}$ взаимно просты и ${\displaystyle m}$ — показатель числа ${\displaystyle a}$ по модулю ${\displaystyle n}$ , то

${\displaystyle m|\lambda (n)}$ .

Другими словами, порядок примитивного корня из единицы в кольце вычетов по модулю ${\displaystyle n}$ делит ${\displaystyle \lambda (n)}$ . В рамках теории групп это утверждение — простое следствие из определения экспоненты группы.

Длина цикла экспоненты

Если для ${\displaystyle n}$ обозначить ${\displaystyle x_{\max }}$ наибольший показатель простых чисел в каноническом разложении ${\displaystyle n}$ , то тогда для всех ${\displaystyle a}$ (включая не взаимно простые с ${\displaystyle n}$ ) и всех ${\displaystyle k\geqslant x_{\max }}$ выполняется

${\displaystyle a^{k}\equiv a^{k+\lambda (n)}{\pmod {n}}}$

В частности, для ${\displaystyle n}$ свободного от квадратов ${\displaystyle n}$ (для него ${\displaystyle x_{\max }=1}$ ), для всех ${\displaystyle a}$

${\displaystyle a\equiv a^{\lambda (n)+1}{\pmod {n}}}$

Средние и типичные значения

Для любого ${\displaystyle x>16}$ и константы ${\displaystyle B}$ :

${\displaystyle {\frac {1}{x}}\sum \limits _{n\leq x}\lambda (n)={\frac {x}{\ln x}}e^{B(1+o(1))\ln \ln x/(\ln \ln \ln x)}}$ .

Здесь

${\displaystyle B=e^{-\gamma }\prod _{p}\left({1-{\frac {1}{(p-1)^{2}(p+1)}}}\right)\approx 0.34537\ .}$

Для любого ${\displaystyle N}$ и для всех ${\displaystyle n\leqslant N}$ , за исключением ${\displaystyle o(N)}$ чисел верно, что:

${\displaystyle \lambda (n)=n/(\ln n)^{\ln \ln \ln n+A+o(1)}}$

где ${\displaystyle A}$ — это постоянная ,

${\displaystyle A=-1+\sum \limits _{p}{\frac {\ln p}{(p-1)^{2}}}\approx 0.2269688\ .}$

Оценки снизу

Для достаточно больших ${\displaystyle N}$ и для любых ${\displaystyle \Delta \geq \ln ^{3}\ln N}$ существует как минимум

${\displaystyle Ne^{-0.69{\sqrt[{3}]{\Delta \ln \Delta }}}}$

натуральных ${\displaystyle n\leq N}$ таких, что ${\displaystyle \lambda (n)\leqslant ne^{-\Delta }}$ .

Для любой последовательности натуральных чисел ${\displaystyle n_{1}<n_{2}<n_{3}<\cdots }$ , любой константы ${\displaystyle 0<c<1/\ln 2}$ и для достаточно большого ${\displaystyle i}$ :

${\displaystyle \lambda (n_{i})>(\ln n_{i})^{c\ln \ln \ln n_{i}}}$ .

Небольшие значения

Для постоянного ${\displaystyle c}$ и достаточно большого положительного ${\displaystyle A}$ существует целое ${\displaystyle n>A}$ такое, что ${\displaystyle \lambda (n)<(\ln A)^{c\ln \ln \ln A}}$ . Более того, такое ${\displaystyle n}$ имеет вид

${\displaystyle n=\prod \limits _{(q-1)|m,\ q{\text{ is prime}}}q}$

при некотором ${\displaystyle m<(\ln A)^{c\ln \ln \ln A}}$ , свободном от квадратов .

Множество значений функции Кармайкла

Множество значений функции Кармайкла, не превосходящих ${\displaystyle x}$ , имеет мощность

${\displaystyle {\frac {x}{\ln ^{\eta +o(1)}x}}\ ,}$

где ${\displaystyle \eta =1-(1+\ln \ln 2)/\ln 2=0.08607\dots }$

См. также

• Число Кармайкла
• Кармайкл, Роберт

Примечания

Литература

• Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. (гл. 11 п.2)
• (англ.) ( ; (англ.) ( ; Schmutz, Eric. Carmichael's lambda function (неопр.) // (англ.) ( . — 1991. — Т. 58 . — С. 363—385 . — ISSN .
• (англ.) ( ; Pomerance, Carl; Shparlinski, Igor E. Period of the power generator and small values of the Carmichael function (англ.) // (англ.) ( : journal. — 2001. — Vol. 70 . — P. 1591—1605, 1803—1806 . — ISSN . — doi : .
• 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. (неопр.) . — Nabu Press. — ISBN 1144400341 .