Функция Кармайкла

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

Малая теорема Ферма — это частный случай теоремы Эйлера, в котором модуль ${\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)}}$^[1][2].

Здесь

${\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}$ — это постоянная^[2][3],

${\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 }}$^[4].

Для любой последовательности натуральных чисел ${\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}}}$^[5][6].

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

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

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

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

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

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

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

• Бухштаб А. А. Теория чисел. — М.: Просвещение, 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.