Меню Главная Случайная статья Настройки Функция Кармайкла Материал из https://ru.wikipedia.org Функция Кармайкла — теоретико-числовая функция, обозначаемая ${\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 Пример 2 Теорема Кармайкла 3 Связь теорем Кармайкла, Эйлера и Ферма 4 Свойства функции Кармайкла 4.1 Делимость 4.2 Функция Кармайкла от НОК 4.3 Примитивные корни из единицы 4.4 Длина цикла экспоненты 4.5 Средние и типичные значения 4.6 Оценки снизу 4.7 Небольшие значения 4.8 Множество значений функции Кармайкла 5 См. также 6 Примечания 7 Литература Пример 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] См. также Число Кармайкла Кармайкл, Роберт Примечания Theorem 3 in Erdos (1991) 1 2 Sandor & Crstici (2004) p.194 Theorem 2 in Erdos (1991) Theorem 5 in Friedlander (2001) 1 2 Theorem 1 in Erdos 1991 1 2 Sandor & Crstici (2004) p.193 Ford, Kevin; Luca, Florian; Pomerance, Carl (27 августа 2014). The image of Carmichael's ?-function. arXiv: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. — .