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

 Функция Кармайкла — теоретико-числовая функция, обозначаемая λ(n)$\lambda (n)$, равная наименьшему показателю m$m$ такому, что
 
  am≡1(modn)$a^m\equiv 1(\mathrm{mod}n)$
  для всех целых a$a$, взаимно простых с модулем n$n$. Говоря языком теории групп, λ(n)$\lambda (n)$ — это экспонента мультипликативной группы вычетов по модулю n$n$.
 Приведем таблицу первых 36 значений функции λ(n)$\lambda (n)$ в сравнении со значениями функции Эйлера φ$\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
λ(n)$\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
φ(n)$\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 и взаимно простые с ним, 12≡1(mod8); 32=9≡1(mod8); 52=25≡1(mod8); 72=49≡1(mod8)$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)$, значит функция Кармайкла λ(8)$\lambda (8)$ равна 2. Функция Эйлера φ(8)$\phi (8)$ равна 4, поскольку в списке 1,3,5,7 ровно 4 числа.
 

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

 Функция Кармайкла λ(n)$\lambda (n)$ от степеней нечётных простых, а также для чисел 2 и 4, равна функции Эйлера φ(n)$\phi (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\} Функция Эйлера для степеней простых есть
 
  φ(pk)=pk−1(p−1).$\phi (p^k)=p^{k-1}(p-1).$
  По основной теореме арифметики любое n>1$n>1$ может быть представлено как
 
  n=pa11pa22…pass$n=p_1^{a_1}{p}_2^{a_2}\dots p_s^{a_s}$
  где $p_10. Вобщемслучае,$.\hspace{1em}Вобщемслучае,$\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}) ].ТеоремаКармайкла Если$ТеоремаКармайкла\hspace{1em}Если$a,nвзаимнопросты,то$взаимнопросты,то$a^{\lambda(n)} \equiv 1 \pmod{n}Иначеговоря,теоремаКармайклаутверждает,чтоопределеннаячерезформулувышефункциядействительноудовлетворяетопределениюфункцииКармайкла.Этатеоремаможетбытьдоказанаспомощьюпервообразныхкорнейикитайскойтеоремыобостатках. =1+2\^kh,то$Иначеговоря,теоремаКармайклаутверждает,чтоопределеннаячерезформулувышефункциядействительноудовлетворяетопределениюфункцииКармайкла.Этатеоремаможетбытьдоказанаспомощьюпервообразныхкорнейикитайскойтеоремыобостатках.\hspace{1em}=1+2\text{^}kh,то$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}. Наконец,если$.\hspace{1em}Наконец,если$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}. Заметимтакже,чтодлялюбых$.\hspace{1em}Заметимтакже,чтодлялюбых$aутверждениенельзяусилить:показатель$утверждениенельзяусилить:показатель$\lambda(n)—минимальный,длякоторого$—минимальный,длякоторого$a^{\lambda(n)}\equiv 1\pmod{n}.Этолегкодоказываетсяотпротивного. Действительно,пустьестьпростое$.Этолегкодоказываетсяотпротивного.\hspace{1em}Действительно,пустьестьпростое$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}$. \}\}
 

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

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

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

 

Делимость

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

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

 Для любых натуральных a,b$a,b$ верно, что
 
  λ(lcm(a,b))=lcm(λ(a),λ(b))$\lambda (\mathrm{l}\mathrm{c}\mathrm{m}(a,b))=\mathrm{l}\mathrm{c}\mathrm{m}(\lambda (a),\lambda (b))$.
  Это сразу получается из определения функции Кармайкла.
 

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

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

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

 Если для n$n$ обозначить xmax$x_{max}$ наибольший показатель простых чисел в каноническом разложении n$n$, то тогда для всех a$a$ (включая не взаимно простые с n$n$) и всех k⩾xmax$k⩾x_{max}$ выполняется
 
  ak≡ak+λ(n)(modn)$a^k\equiv a^{k+\lambda (n)}(\mathrm{mod}n)$
  В частности, для n$n$ свободного от квадратов n$n$ (для него xmax=1$x_{max}=1$), для всех a$a$
 
  a≡aλ(n)+1(modn)$a\equiv a^{\lambda (n)+1}(\mathrm{mod}n)$
 

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

 Для любого x>16$x>16$ и константы B$B$:
 
  1x∑n≤xλ(n)=xlnxeB(1+o(1))lnlnx/(lnlnlnx)$\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−γ∏p(1−1(p−1)2(p+1))≈0.34537 .$B=e^{-\gamma }\prod _p\left(1-\frac{1}{(p-1{)}^2(p+1)}\right)\approx 0.34537.$
  Для любого N$N$ и для всех n⩽N$n⩽N$, за исключением o(N)$o(N)$ чисел верно, что:
 
  λ(n)=n/(lnn)lnlnlnn+A+o(1)$\lambda (n)=n/(\ln n{)}^{\ln \ln \ln n+A+o(1)}$
  где A$A$ — это постоянная,
 
  A=−1+∑plnp(p−1)2≈0.2269688 .$A=-1+\sum _p\frac{\ln p}{(p-1{)}^2}\approx 0.2269688.$
 

Оценки снизу

 Для достаточно больших N$N$ и для любых Δ≥ln3lnN$\mathrm{\Delta }\ge {\ln }^3\ln N$ существует как минимум
 
  Ne−0.69ΔlnΔ√3$N{e}^{-0.69\sqrt[3]{\mathrm{\Delta }\ln \mathrm{\Delta }}}$
  натуральных n≤N$n\le N$ таких, что λ(n)⩽ne−Δ$\lambda (n)⩽n{e}^{-\mathrm{\Delta }}$.
 Для любой последовательности натуральных чисел $n_1 
  λ(ni)>(lnni)clnlnlnni$\lambda (n_i)>(\ln n_i{)}^{c\ln \ln \ln n_i}$.
 

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

 Для постоянного c$c$ и достаточно большого положительного A$A$ существует целое n>A$n>A$ такое, что λ(n)<(lnA)clnlnlnA$\lambda (n)<(\ln A{)}^{c\ln \ln \ln A}$. Более того, такое n$n$ имеет вид
 
  n=∏(q−1)|m, q is primeq$n=\prod _{(q-1)|m,q\text{ is prime}}q$
  при некотором m<(lnA)clnlnlnA$m<(\ln A{)}^{c\ln \ln \ln A}$, свободном от квадратов.
 

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

 Множество значений функции Кармайкла, не превосходящих x$x$, имеет мощность
 
  xlnη+o(1)x ,$\frac{x}{{\ln }^{\eta +o(1)}x},$
  где η=1−(1+lnln2)/ln2=0.08607…$\eta =1-(1+\ln \ln 2)/\ln 2=0.08607\dots$