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

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

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

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

Приведём таблицу первых 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 {HOK} [\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}}

.

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

Поскольку функция Кармайкла $\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 {HOK} (a,b))=\mathrm {HOK} (\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\

, где

\mathbf {e} ^{\mathbf {-\gamma } }

— экспонента от постоянной Эйлера — Маскерони (

\gamma \approx 0.57721

)^[2].

Для любого $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{ - простое}}}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$

↑ Кноп К. А. Азы теории чисел. — М., 2017. — С. 41.
↑ Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М., 1974. — С. 740.

Бухштаб А. А. . Теория чисел. — М.: Просвещение, 1966. — 386 с.
Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел / пер. с англ. С. П. Дёмушкина. — М.: Мир, 1987. — 416 с.
Кноп К. А. Азы теории чисел. — М.: МЦНМО, 2017. — 80 с. — ISBN 978-5-4439-1126-7.
Пастухов Ю. Ф., Волосова Н. К. Несколько теорем о числах Кармайкла: Учебное пособие. — М., 2023. — 33 с.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров: определения, теоремы, формулы / под общ. ред. И. Г. Арамановича. — М.: Наука, 1974. — 832 с.

[1] Кноп К. А. Азы теории чисел. — М., 2017. — С. 41.

[2] Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М., 1974. — С. 740.

[1]

[2]

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

Пример

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

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

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

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

Делимость

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

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

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

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

Оценки снизу

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

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

Примечания

Литература

Дополнительно по теме

Категории