Функция Кармайкла — теоретико-числовая функция , обозначаемая λ ( n ) {\displaystyle \lambda (n)} , равная наименьшему показателю m {\displaystyle m} такому, что
a m ≡ 1 ( mod n ) {\displaystyle a^{m}\equiv 1{\pmod {n}}} для всех целых a {\displaystyle a} , взаимно простых с модулем n {\displaystyle n} . Говоря языком теории групп, λ ( n ) {\displaystyle \lambda (n)} — это экспонента мультипликативной группы вычетов по модулю n {\displaystyle n} .
Приведем таблицу первых 36 значений функции λ ( n ) {\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 λ ( n ) {\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 φ ( n ) {\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,3,5,7 — все числа, меньшие 8 и взаимно простые с ним, 1 2 ≡ 1 ( mod 8 ) ; 3 2 = 9 ≡ 1 ( mod 8 ) ; 5 2 = 25 ≡ 1 ( mod 8 ) ; 7 2 = 49 ≡ 1 ( mod 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}}} , значит функция Кармайкла λ ( 8 ) {\displaystyle \lambda (8)} равна 2. Функция Эйлера φ ( 8 ) {\displaystyle \varphi (8)} равна 4, поскольку в списке 1,3,5,7 ровно 4 числа.
Функция Кармайкла λ ( n ) {\displaystyle \lambda (n)} от степеней нечётных простых, а также для чисел 2 и 4, равна функции Эйлера φ ( n ) {\displaystyle \varphi (n)} ; для степеней двойки, больших 4, она равна половине функции Эйлера:
λ ( n ) = { 1 2 φ ( n ) , если n = 2 k , k ⩾ 3 , т.е. n = 8 , 16 , 32 , 64 , 128 , 256 , … φ ( n ) , если n ∈ { 2 , 4 } или n = p k , p ∈ P , p > 2 , т.е. n = 2 , 3 k , 4 , 5 k , 7 k , 11 k , 13 k , 17 k , … {\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}}} Функция Эйлера для степеней простых есть
φ ( p k ) = p k − 1 ( p − 1 ) . {\displaystyle \varphi (p^{k})=p^{k-1}(p-1).\;} По основной теореме арифметики любое n > 1 {\displaystyle n>1} может быть представлено как
n = p 1 a 1 p 2 a 2 … p s a s {\displaystyle n=p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{s}^{a_{s}}} где p 1 < p 2 < ⋯ < p s {\displaystyle p_{1}<p_{2}<\dots <p_{s}} — простые числа , а все a i > 0 {\displaystyle a_{i}>0} .
В общем случае, λ ( n ) {\displaystyle \lambda (n)} — это наименьшее общее кратное λ ( p i a i ) {\displaystyle \lambda (p_{i}^{a_{i}})} всех точных степеней простых, входящих в разложение n {\displaystyle n} на множители:
λ ( n ) = lcm [ λ ( p 1 a 1 ) , λ ( p 2 a 2 ) , … , λ ( p s a s ) ] . {\displaystyle \lambda (n)=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{s}^{a_{s}})].} Теорема Кармайкла Если a , n {\displaystyle a,n} взаимно просты, то
a λ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}} Иначе говоря, теорема Кармайкла утверждает, что определенная через формулу выше функция действительно удовлетворяет определению функции Кармайкла. Эта теорема может быть доказана с помощью первообразных корней и китайской теоремы об остатках .
Докажем сначала, что для всех a {\displaystyle a} взаимно простых с n {\displaystyle n} выполняется a λ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}} .
По малой теореме Ферма для любого простого модуля p {\displaystyle p} и любого a {\displaystyle a} , взаимно простого с модулем имеем a p − 1 = 1 + h p {\displaystyle a^{p-1}=1+hp} .
Если a p k − 1 ( p − 1 ) = 1 + h p k {\displaystyle a^{p^{k-1}(p-1)}=1+hp^{k}} , то
a p k ( p − 1 ) = ( 1 + h p k ) p = 1 + h p p p k + ⋯ = 1 + h 0 p k + 1 {\displaystyle a^{p^{k}(p-1)}=(1+hp^{k})^{p}=1+h^{p}pp^{k}+\dots =1+h_{0}p^{k+1}}
Тогда по методу математической индукции мы получаем, что для всех a {\displaystyle a} a p k − 1 ( p − 1 ) = a λ ( p k ) ≡ 1 ( mod p k ) {\displaystyle a^{p^{k-1}(p-1)}=a^{\lambda (p^{k})}\equiv 1{\pmod {p^{k}}}} .
Для модуля 2 соотношение несколько сильнее:
Если a {\displaystyle a} нечётно, то a = 1 + 2 h {\displaystyle a=1+2h} .
Тогда a 2 = 1 + 4 h ( h + 1 ) = 1 + 8 C h + 1 2 {\displaystyle a^{2}=1+4h(h+1)=1+8C_{h+1}^{2}} .
Далее, если a 2 k − 2 = 1 + 2 k h {\displaystyle 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 ) {\displaystyle a^{2^{k-1}}=(1+2^{k}h)^{2}=1+2^{k+1}(h+2^{k-1}h^{2})}
Тогда по математической индукции мы получаем, что для всех нечётных a {\displaystyle a} при k ⩾ 3 {\displaystyle k\geqslant 3} верно, что a 2 k − 2 = a λ ( 2 k ) ≡ 1 ( mod 2 k ) {\displaystyle a^{2^{k-2}}=a^{\lambda (2^{k})}\equiv 1{\pmod {2^{k}}}} .
Наконец, если n = 2 k p 1 a 1 … p s a s {\displaystyle n=2^{k}p_{1}^{a_{1}}\dots p_{s}^{a_{s}}} и a {\displaystyle a} взаимно просто с n {\displaystyle n} , то a λ ( p j a j ) ≡ 1 ( mod p j a j ) {\displaystyle a^{\lambda (p_{j}^{a_{j}})}\equiv 1{\pmod {p_{j}^{a_{j}}}}} и a λ ( 2 k ) ≡ 1 ( mod 2 k ) {\displaystyle a^{\lambda (2^{k})}\equiv 1{\pmod {2^{k}}}} , значит a λ ( n ) ≡ 1 ( mod p j a j ) {\displaystyle a^{\lambda (n)}\equiv 1{\pmod {p_{j}^{a_{j}}}}} и a λ ( n ) ≡ 1 ( mod 2 k ) {\displaystyle a^{\lambda (n)}\equiv 1{\pmod {2^{k}}}} и тогда a λ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}} .
Заметим также, что для любых a {\displaystyle a} утверждение нельзя усилить: показатель λ ( n ) {\displaystyle \lambda (n)} — минимальный, для которого a λ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}} . Это легко доказывается от противного.
Действительно, пусть есть простое q {\displaystyle q} такое, что для всех a {\displaystyle a} a λ ( n ) / q ≡ 1 ( mod n ) {\displaystyle a^{\lambda (n)/q}\equiv 1{\pmod {n}}} . Поскольку λ ( n ) = lcm [ λ ( p 1 a 1 ) , λ ( p 2 a 2 ) , … , λ ( p s a s ) ] . {\displaystyle \lambda (n)=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{s}^{a_{s}})].} , то q {\displaystyle q} делит какое-то λ ( p i a i ) {\displaystyle \lambda (p_{i}^{a_{i}})} , то есть для всех a {\displaystyle a} a λ ( p i a i ) / q ≡ 1 ( mod p i a i ) {\displaystyle a^{\lambda (p_{i}^{a_{i}})/q}\equiv 1{\pmod {p_{i}^{a_{i}}}}} . Однако это противоречит тому факту, что группа Z p k × {\displaystyle \mathbb {Z} _{p^{k}}^{\times }} циклична при p > 2 {\displaystyle p>2} , а при p = 2 {\displaystyle p=2} — противоречит тому факту, что группа Z 2 k × {\displaystyle \mathbb {Z} _{2^{k}}^{\times }} имеет экспоненту 2 k − 2 {\displaystyle 2^{k-2}} . ■
Поскольку функция Кармайкла λ ( n ) {\displaystyle \lambda (n)} делит функцию Эйлера φ ( n ) {\displaystyle \varphi (n)} (последовательность их частных см. в последовательность A034380 в OEIS ), теорема Кармайкла является более сильным результатом, чем классическая теорема Эйлера . Ясно, что теорема Кармайкла связана с теоремой Эйлера , потому что экспонента конечной абелевой группы всегда делит порядок группы. Функции Кармайкла и Эйлера отличаются уже при небольших аргументах: λ ( 15 ) = 4 {\displaystyle \lambda (15)=4} , но φ ( 15 ) = 8 {\displaystyle \varphi (15)=8} , они отличаются всегда, когда группа вычетов по модулю n {\displaystyle n} не имеет образующей (см. последовательность A033949 ).
Малая теорема Ферма — это частный случай теоремы Эйлера, в котором модуль n {\displaystyle n} — это простое число. Теорема Кармайкла для простых модулей дает то же утверждение, поскольку группа вычетов по простому модулю является цикличной , то есть её порядок и экспонента совпадают.
a | b ⇒ λ ( a ) | λ ( b ) {\displaystyle a|b\Rightarrow \lambda (a)|\lambda (b)} Для любых натуральных a , b {\displaystyle a,b} верно, что
λ ( l c m ( a , b ) ) = l c m ( λ ( a ) , λ ( b ) ) {\displaystyle \lambda (\mathrm {lcm} (a,b))=\mathrm {lcm} (\lambda (a),\lambda (b))} . Это сразу получается из определения функции Кармайкла.
Если a , n {\displaystyle a,n} взаимно просты и m {\displaystyle m} — показатель числа a {\displaystyle a} по модулю n {\displaystyle n} , то
m | λ ( n ) {\displaystyle m|\lambda (n)} . Другими словами, порядок примитивного корня из единицы в кольце вычетов по модулю n {\displaystyle n} делит λ ( n ) {\displaystyle \lambda (n)} . В рамках теории групп это утверждение — простое следствие из определения экспоненты группы.
Если для n {\displaystyle n} обозначить x max {\displaystyle x_{\max }} наибольший показатель простых чисел в каноническом разложении n {\displaystyle n} , то тогда для всех a {\displaystyle a} (включая не взаимно простые с n {\displaystyle n} ) и всех k ⩾ x max {\displaystyle k\geqslant x_{\max }} выполняется
a k ≡ a k + λ ( n ) ( mod n ) {\displaystyle a^{k}\equiv a^{k+\lambda (n)}{\pmod {n}}} В частности, для n {\displaystyle n} свободного от квадратов n {\displaystyle n} (для него x max = 1 {\displaystyle x_{\max }=1} ), для всех a {\displaystyle a}
a ≡ a λ ( n ) + 1 ( mod n ) {\displaystyle a\equiv a^{\lambda (n)+1}{\pmod {n}}} Для любого x > 16 {\displaystyle x>16} и константы B {\displaystyle B} :
1 x ∑ n ≤ x λ ( n ) = x ln x e B ( 1 + o ( 1 ) ) ln ln x / ( ln ln ln x ) {\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] . Здесь
B = e − γ ∏ p ( 1 − 1 ( p − 1 ) 2 ( p + 1 ) ) ≈ 0.34537 . {\displaystyle B=e^{-\gamma }\prod _{p}\left({1-{\frac {1}{(p-1)^{2}(p+1)}}}\right)\approx 0.34537\ .} Для любого N {\displaystyle N} и для всех n ⩽ N {\displaystyle n\leqslant N} , за исключением o ( N ) {\displaystyle o(N)} чисел верно, что:
λ ( n ) = n / ( ln n ) ln ln ln n + A + o ( 1 ) {\displaystyle \lambda (n)=n/(\ln n)^{\ln \ln \ln n+A+o(1)}} где A {\displaystyle A} — это постоянная[ 2] [ 3] ,
A = − 1 + ∑ p ln p ( p − 1 ) 2 ≈ 0.2269688 . {\displaystyle A=-1+\sum \limits _{p}{\frac {\ln p}{(p-1)^{2}}}\approx 0.2269688\ .} Для достаточно больших N {\displaystyle N} и для любых Δ ≥ ln 3 ln N {\displaystyle \Delta \geq \ln ^{3}\ln N} существует как минимум
N e − 0.69 Δ ln Δ 3 {\displaystyle Ne^{-0.69{\sqrt[{3}]{\Delta \ln \Delta }}}} натуральных n ≤ N {\displaystyle n\leq N} таких, что λ ( n ) ⩽ n e − Δ {\displaystyle \lambda (n)\leqslant ne^{-\Delta }} [ 4] .
Для любой последовательности натуральных чисел n 1 < n 2 < n 3 < ⋯ {\displaystyle n_{1}<n_{2}<n_{3}<\cdots } , любой константы 0 < c < 1 / ln 2 {\displaystyle 0<c<1/\ln 2} и для достаточно большого i {\displaystyle i} :
λ ( n i ) > ( ln n i ) c ln ln ln n i {\displaystyle \lambda (n_{i})>(\ln n_{i})^{c\ln \ln \ln n_{i}}} [ 5] [ 6] . Для постоянного c {\displaystyle c} и достаточно большого положительного A {\displaystyle A} существует целое n > A {\displaystyle n>A} такое, что λ ( n ) < ( ln A ) c ln ln ln A {\displaystyle \lambda (n)<(\ln A)^{c\ln \ln \ln A}} [ 6] . Более того, такое n {\displaystyle n} имеет вид
n = ∏ ( q − 1 ) | m , q is prime q {\displaystyle n=\prod \limits _{(q-1)|m,\ q{\text{ is prime}}}q} при некотором m < ( ln A ) c ln ln ln A {\displaystyle m<(\ln A)^{c\ln \ln \ln A}} , свободном от квадратов[ 5] .
Множество значений функции Кармайкла, не превосходящих x {\displaystyle x} , имеет мощность
x ln η + o ( 1 ) x , {\displaystyle {\frac {x}{\ln ^{\eta +o(1)}x}}\ ,} где η = 1 − ( 1 + ln ln 2 ) / ln 2 = 0.08607 … {\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 August 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 . 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 .