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

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

$a^m\equiv 1(\mathrm{mod}n)$

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

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

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

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

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

$\lambda (n)=\{\begin{array}{cc}\frac{1}{2}\phi (n),& \text{если }n=2^k,k⩾3,\text{ т.е. }n=8,16,32,64,128,256,\dots \\ \phi (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{array}$

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

$\phi (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)=\mathrm{lcm}[\lambda (p_1^{a_1}),\lambda (p_2^{a_2}),\dots ,\lambda (p_s^{a_s})].$

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

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

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

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

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

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

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

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

Делимость

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

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

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

$\lambda (\mathrm{l}\mathrm{c}\mathrm{m}(a,b))=\mathrm{l}\mathrm{c}\mathrm{m}(\lambda (a),\lambda (b))$.

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

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

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

$m|\lambda (n)$ .

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

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

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

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

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

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

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

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

$\frac{1}{x}\sum _{n\le 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⩽N$, за исключением $o(N)$ чисел верно, что:

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

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

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

Оценки снизу

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

$N{e}^{-0.69\sqrt[3]{\mathrm{\Delta }\ln \mathrm{\Delta }}}$

натуральных $n\le N$ таких, что $\lambda (n)⩽n{e}^{-\mathrm{\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 _{(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)
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга