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

Функция Кармайкла — теоретико-числовая функция, обозначаемая ${\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 a}$ взаимно простых с ${\displaystyle n}$ выполняется ${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поскольку функция Кармайкла ${\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]

См. также

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