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

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

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

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

Приведем таблицу первых 36 значений функции $\lambda (n)$ последовательность A002322 в OEIS в сравнении со значениями функции Эйлера $\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
$\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
$\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 и взаимно простые с ним, $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}}$, значит функция Кармайкла $\lambda (8)$ равна 2. Функция Эйлера $\varphi (8)$ равна 4, поскольку в списке 1,3,5,7 ровно 4 числа.

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

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

$\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}}$

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

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

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

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

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

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

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

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

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

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

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

Доказательство

Докажем сначала, что для всех $a$ взаимно простых с $n$ выполняется $a^{\lambda (n)}\equiv 1{\pmod {n}}$.

По малой теореме Ферма для любого простого модуля $p$ и любого $a$, взаимно простого с модулем имеем $a^{p-1}=1+hp$.

Если $a^{p^{k-1}(p-1)}=1+hp^{k}$, то

$a^{p^{k}(p-1)}=(1+hp^{k})^{p}=1+h^{p}pp^{k}+\dots =1+h_{0}p^{k+1}$

Тогда по методу математической индукции мы получаем, что для всех $a$ $a^{p^{k-1}(p-1)}=a^{\lambda (p^{k})}\equiv 1{\pmod {p^{k}}}$.

Для модуля 2 соотношение несколько сильнее:

Если $a$ нечётно, то $a=1+2h$.

Тогда $a^{2}=1+4h(h+1)=1+8C_{h+1}^{2}$.

Далее, если $a^{2^{k-2}}=1+2^{k}h$, то

$a^{2^{k-1}}=(1+2^{k}h)^{2}=1+2^{k+1}(h+2^{k-1}h^{2})$

Тогда по математической индукции мы получаем, что для всех нечётных $a$ при $k\geqslant 3$ верно, что $a^{2^{k-2}}=a^{\lambda (2^{k})}\equiv 1{\pmod {2^{k}}}$.

Наконец, если $n=2^{k}p_{1}^{a_{1}}\dots p_{s}^{a_{s}}$ и $a$ взаимно просто с $n$, то $a^{\lambda (p_{j}^{a_{j}})}\equiv 1{\pmod {p_{j}^{a_{j}}}}$ и $a^{\lambda (2^{k})}\equiv 1{\pmod {2^{k}}}$, значит $a^{\lambda (n)}\equiv 1{\pmod {p_{j}^{a_{j}}}}$ и $a^{\lambda (n)}\equiv 1{\pmod {2^{k}}}$ и тогда $a^{\lambda (n)}\equiv 1{\pmod {n}}$.

Заметим также, что для любых $a$ утверждение нельзя усилить: показатель $\lambda (n)$ — минимальный, для которого $a^{\lambda (n)}\equiv 1{\pmod {n}}$. Это легко доказывается от противного.

Действительно, пусть есть простое $q$ такое, что для всех $a$ $a^{\lambda (n)/q}\equiv 1{\pmod {n}}$. Поскольку $\lambda (n)=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{s}^{a_{s}})].$, то $q$ делит какое-то $\lambda (p_{i}^{a_{i}})$, то есть для всех $a$ $a^{\lambda (p_{i}^{a_{i}})/q}\equiv 1{\pmod {p_{i}^{a_{i}}}}$. Однако это противоречит тому факту, что группа $\mathbb {Z} _{p^{k}}^{\times }$ циклична при $p>2$, а при $p=2$ — противоречит тому факту, что группа $\mathbb {Z} _{2^{k}}^{\times }$ имеет экспоненту $2^{k-2}$. ■

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

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

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

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

Делимость

$a|b\Rightarrow \lambda (a)|\lambda (b)$

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

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

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

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

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

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

$m|\lambda (n)$ .

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

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

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

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

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

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

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

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

${\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)}$.

Здесь

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

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

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

где $A$ — это постоянная,

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

Оценки снизу

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Литература

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