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

Функция Кармайкла — теоретико-числовая функция, обозначаемая $\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}\;\;\varphi (n)&{\text{if }}n=2,3,4,5,6,7,9,10,11,13,14,17,18,19,22,23,25,26,27,29\dots \\{\frac {1}{2}}\varphi (n)&{\text{if }}n=8,16,32,64,128,256\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)}

[1][2].

Здесь

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

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

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

[5][6].

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

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

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

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

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

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

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

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

См. также

Примечания

Theorem 3 in Erdos (1991)
Sandor & Crstici (2004) p.194
Theorem 2 in Erdos (1991)
Theorem 5 in Friedlander (2001)
Theorem 1 in Erdos 1991
Sandor & Crstici (2004) p.193
Ford, Kevin; Luca, Florian & Pomerance, Carl (27 August 2014), The image of Carmichael's ?-function, arΧiv:1408.6506 [math.NT]

Литература

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Theorem 3 in Erdos (1991)

[HBII194-2] Sandor & Crstici (2004) p.194

[3] Theorem 2 in Erdos (1991)

[4] Theorem 5 in Friedlander (2001)

[Theorem_1_in_Erdos_1991-5] Theorem 1 in Erdos 1991

[HBII193-6] Sandor & Crstici (2004) p.193

[7] Ford, Kevin; Luca, Florian & Pomerance, Carl (27 August 2014), The image of Carmichael's ?-function, arΧiv:1408.6506 [math.NT]