Функция Кармайкла
Функция Кармайкла — теоретико-числовая функция, обозначаемая [math]\displaystyle{ \lambda(n) }[/math], равная наименьшему показателю [math]\displaystyle{ m }[/math] такому, что
- [math]\displaystyle{ a^m \equiv 1 \pmod{n} }[/math]
для всех целых [math]\displaystyle{ a }[/math], взаимно простых с модулем [math]\displaystyle{ n }[/math]. Говоря языком теории групп, [math]\displaystyle{ \lambda(n) }[/math] — это экспонента мультипликативной группы вычетов по модулю [math]\displaystyle{ n }[/math].
Приведем таблицу первых 36 значений функции [math]\displaystyle{ \lambda(n) }[/math] последовательность A002322 в OEIS в сравнении со значениями функции Эйлера [math]\displaystyle{ \varphi }[/math]. (жирным выделены отличающиеся значения)
| 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 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| [math]\displaystyle{ \lambda(n) }[/math] | 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 |
| [math]\displaystyle{ \varphi(n) }[/math] | 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 и взаимно простые с ним, [math]\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} }[/math], значит функция Кармайкла [math]\displaystyle{ \lambda(8) }[/math] равна 2. Функция Эйлера [math]\displaystyle{ \varphi(8) }[/math] равна 4, поскольку в списке 1,3,5,7 ровно 4 числа.
Теорема Кармайкла
Функция Кармайкла [math]\displaystyle{ \lambda(n) }[/math] от степеней нечётных простых, а также для чисел 2 и 4, равна функции Эйлера [math]\displaystyle{ \varphi(n) }[/math]; для степеней двойки, больших 4, она равна половине функции Эйлера:
- [math]\displaystyle{ \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} }[/math]
Функция Эйлера для степеней простых есть
- [math]\displaystyle{ \varphi(p^k) = p^{k-1}(p-1).\; }[/math]
По основной теореме арифметики любое [math]\displaystyle{ n\gt 1 }[/math] может быть представлено как
- [math]\displaystyle{ n= p_1^{a_1}p_2^{a_2} \dots p_s^{a_s} }[/math]
где [math]\displaystyle{ p_1\lt p_2\lt \dots \lt p_s }[/math] — простые числа, а все [math]\displaystyle{ a_i\gt 0 }[/math].
В общем случае, [math]\displaystyle{ \lambda(n) }[/math] — это наименьшее общее кратное [math]\displaystyle{ \lambda(p_i^{a_i}) }[/math] всех точных степеней простых, входящих в разложение [math]\displaystyle{ n }[/math] на множители:
- [math]\displaystyle{ \lambda(n) = \operatorname{lcm}[\lambda(p_1^{a_1}),\;\lambda(p_2^{a_2}),\dots,\lambda(p_s^{a_s}) ]. }[/math]
- Теорема Кармайкла
Если [math]\displaystyle{ a,n }[/math] взаимно просты, то
- [math]\displaystyle{ a^{\lambda(n)} \equiv 1 \pmod{n} }[/math]
Иначе говоря, теорема Кармайкла утверждает, что определенная через формулу выше функция действительно удовлетворяет определению функции Кармайкла. Эта теорема может быть доказана с помощью первообразных корней и китайской теоремы об остатках.
Докажем сначала, что для всех [math]\displaystyle{ a }[/math] взаимно простых с [math]\displaystyle{ n }[/math] выполняется [math]\displaystyle{ a^{\lambda(n)}\equiv 1\pmod{n} }[/math].
По малой теореме Ферма для любого простого модуля [math]\displaystyle{ p }[/math] и любого [math]\displaystyle{ a }[/math], взаимно простого с модулем имеем [math]\displaystyle{ a^{p-1}=1+hp }[/math].
Если [math]\displaystyle{ a^{p^{k-1}(p-1)}=1+hp^k }[/math], то
[math]\displaystyle{ a^{p^k(p-1)}=(1+hp^k)^p=1+h^p p p^k+\dots=1+h_0 p^{k+1} }[/math]
Тогда по методу математической индукции мы получаем, что для всех [math]\displaystyle{ a }[/math] [math]\displaystyle{ a^{p^{k-1}(p-1)} = a^{\lambda(p^k)} \equiv 1\pmod{p^k} }[/math].
Для модуля 2 соотношение несколько сильнее:
Если [math]\displaystyle{ a }[/math] нечётно, то [math]\displaystyle{ a=1+2h }[/math].
Тогда [math]\displaystyle{ a^2=1+4h(h+1)=1+8C_{h+1}^2 }[/math].
Далее, если [math]\displaystyle{ a^{2^{k-2}}=1+2^k h }[/math], то
[math]\displaystyle{ a^{2^{k-1}}=(1+2^k h)^2=1+2^{k+1}(h+2^{k-1}h^2) }[/math]
Тогда по математической индукции мы получаем, что для всех нечётных [math]\displaystyle{ a }[/math] при [math]\displaystyle{ k\geqslant 3 }[/math] верно, что [math]\displaystyle{ a^{2^{k-2}}= a^{\lambda(2^k)}\equiv 1\pmod{2^k} }[/math].
Наконец, если [math]\displaystyle{ n=2^k p_1^{a_1} \dots p_s^{a_s} }[/math] и [math]\displaystyle{ a }[/math] взаимно просто с [math]\displaystyle{ n }[/math], то [math]\displaystyle{ a^{\lambda(p_j^{a_j})} \equiv 1\pmod{p_j^{a_j}} }[/math] и [math]\displaystyle{ a^{\lambda(2^k)}\equiv 1\pmod{2^k} }[/math], значит [math]\displaystyle{ a^{\lambda(n)} \equiv 1\pmod{p_j^{a_j}} }[/math] и [math]\displaystyle{ a^{\lambda(n)}\equiv 1\pmod{2^k} }[/math] и тогда [math]\displaystyle{ a^{\lambda(n)}\equiv 1\pmod{n} }[/math].
Заметим также, что для любых [math]\displaystyle{ a }[/math] утверждение нельзя усилить: показатель [math]\displaystyle{ \lambda(n) }[/math] — минимальный, для которого [math]\displaystyle{ a^{\lambda(n)}\equiv 1\pmod{n} }[/math]. Это легко доказывается от противного.
Действительно, пусть есть простое [math]\displaystyle{ q }[/math] такое, что для всех [math]\displaystyle{ a }[/math] [math]\displaystyle{ a^{\lambda(n)/q}\equiv 1\pmod{n} }[/math]. Поскольку [math]\displaystyle{ \lambda(n) = \operatorname{lcm}[\lambda(p_1^{a_1}),\;\lambda(p_2^{a_2}),\dots,\lambda(p_s^{a_s}) ]. }[/math], то [math]\displaystyle{ q }[/math] делит какое-то [math]\displaystyle{ \lambda(p_i^{a_i}) }[/math], то есть для всех [math]\displaystyle{ a }[/math] [math]\displaystyle{ a^{\lambda(p_i^{a_i})/q}\equiv 1\pmod{p_i^{a_i}} }[/math]. Однако это противоречит тому факту, что группа [math]\displaystyle{ \mathbb{Z}_{p^k}^{\times} }[/math] циклична при [math]\displaystyle{ p\gt 2 }[/math], а при [math]\displaystyle{ p=2 }[/math] — противоречит тому факту, что группа [math]\displaystyle{ \mathbb{Z}_{2^k}^{\times} }[/math] имеет экспоненту [math]\displaystyle{ 2^{k-2} }[/math]. ■
Связь теорем Кармайкла, Эйлера и Ферма
Поскольку функция Кармайкла [math]\displaystyle{ \lambda(n) }[/math] делит функцию Эйлера [math]\displaystyle{ \varphi(n) }[/math] (последовательность их частных см. в последовательность A034380 в OEIS), теорема Кармайкла является более сильным результатом, чем классическая теорема Эйлера. Ясно, что теорема Кармайкла связана с теоремой Эйлера, потому что экспонента конечной абелевой группы всегда делит порядок группы. Функции Кармайкла и Эйлера отличаются уже при небольших аргументах: [math]\displaystyle{ \lambda(15)=4 }[/math], но [math]\displaystyle{ \varphi(15)=8 }[/math], они отличаются всегда, когда группа вычетов по модулю [math]\displaystyle{ n }[/math] не имеет образующей (см. последовательность A033949).
Малая теорема Ферма — это частный случай теоремы Эйлера, в котором модуль [math]\displaystyle{ n }[/math] — это простое число. Теорема Кармайкла для простых модулей дает то же утверждение, поскольку группа вычетов по простому модулю является цикличной, то есть её порядок и экспонента совпадают.
Свойства функции Кармайкла
Делимость
- [math]\displaystyle{ a|b \Rightarrow \lambda(a)|\lambda(b) }[/math]
Функция Кармайкла от НОК
Для любых натуральных [math]\displaystyle{ a, b }[/math] верно, что
- [math]\displaystyle{ \lambda(\mathrm{lcm}(a,b)) = \mathrm{lcm}( \lambda(a), \lambda(b) ) }[/math].
Это сразу получается из определения функции Кармайкла.
Примитивные корни из единицы
Если [math]\displaystyle{ a,n }[/math] взаимно просты и [math]\displaystyle{ m }[/math] — показатель числа [math]\displaystyle{ a }[/math] по модулю [math]\displaystyle{ n }[/math], то
- [math]\displaystyle{ m | \lambda(n) }[/math] .
Другими словами, порядок примитивного корня из единицы в кольце вычетов по модулю [math]\displaystyle{ n }[/math] делит [math]\displaystyle{ \lambda(n) }[/math]. В рамках теории групп это утверждение — простое следствие из определения экспоненты группы.
Длина цикла экспоненты
Если для [math]\displaystyle{ n }[/math] обозначить [math]\displaystyle{ x_{\max} }[/math] наибольший показатель простых чисел в каноническом разложении [math]\displaystyle{ n }[/math], то тогда для всех [math]\displaystyle{ a }[/math] (включая не взаимно простые с [math]\displaystyle{ n }[/math]) и всех [math]\displaystyle{ k \geqslant x_{\max} }[/math] выполняется
- [math]\displaystyle{ a^k \equiv a^{k+\lambda(n)} \pmod n }[/math]
В частности, для [math]\displaystyle{ n }[/math] свободного от квадратов [math]\displaystyle{ n }[/math] (для него [math]\displaystyle{ x_{\max} = 1 }[/math]), для всех [math]\displaystyle{ a }[/math]
- [math]\displaystyle{ a \equiv a^{\lambda(n)+1} \pmod n }[/math]
Средние и типичные значения
Для любого [math]\displaystyle{ x\gt 16 }[/math] и константы [math]\displaystyle{ B }[/math]:
- [math]\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) } }[/math][1][2].
Здесь
- [math]\displaystyle{ B = e^{-\gamma} \prod_p \left({1 - \frac{1}{(p-1)^2(p+1)}}\right) \approx 0.34537 \ . }[/math]
Для любого [math]\displaystyle{ N }[/math] и для всех [math]\displaystyle{ n\leqslant N }[/math], за исключением [math]\displaystyle{ o(N) }[/math] чисел верно, что:
- [math]\displaystyle{ \lambda(n) = n / (\ln n)^{\ln\ln\ln n + A + o(1)} }[/math]
где [math]\displaystyle{ A }[/math] — это постоянная[2][3],
- [math]\displaystyle{ A = -1 + \sum\limits_p \frac{\ln p}{(p-1)^2} \approx 0.2269688 \ . }[/math]
Оценки снизу
Для достаточно больших [math]\displaystyle{ N }[/math] и для любых [math]\displaystyle{ \Delta \geq \ln^3\ln N }[/math] существует как минимум
- [math]\displaystyle{ Ne^{-0.69\sqrt[3]{\Delta\ln\Delta}} }[/math]
натуральных [math]\displaystyle{ n \leq N }[/math] таких, что [math]\displaystyle{ \lambda(n) \leqslant ne^{-\Delta} }[/math][4].
Для любой последовательности натуральных чисел [math]\displaystyle{ n_1\lt n_2\lt n_3\lt \cdots }[/math], любой константы [math]\displaystyle{ 0\lt c\lt 1/\ln2 }[/math] и для достаточно большого [math]\displaystyle{ i }[/math]:
Небольшие значения
Для постоянного [math]\displaystyle{ c }[/math] и достаточно большого положительного [math]\displaystyle{ A }[/math] существует целое [math]\displaystyle{ n\gt A }[/math] такое, что [math]\displaystyle{ \lambda(n)\lt (\ln A)^{c\ln\ln\ln A} }[/math][6]. Более того, такое [math]\displaystyle{ n }[/math] имеет вид
- [math]\displaystyle{ n=\prod\limits_{(q-1)|m, \ q \text{ is prime}}q }[/math]
при некотором [math]\displaystyle{ m\lt (\ln A)^{c\ln\ln\ln A} }[/math], свободном от квадратов[5].
Множество значений функции Кармайкла
Множество значений функции Кармайкла, не превосходящих [math]\displaystyle{ x }[/math], имеет мощность
- [math]\displaystyle{ \frac{x}{\ln^{\eta+o(1)}x} \ , }[/math]
где [math]\displaystyle{ \eta = 1-(1+\ln \ln 2)/\ln 2=0.08607\dots }[/math][7]
См. также
Примечания
- ↑ Theorem 3 in Erdos (1991)
- ↑ 2,0 2,1 Sandor & Crstici (2004) p.194
- ↑ Theorem 2 in Erdos (1991)
- ↑ Theorem 5 in Friedlander (2001)
- ↑ 5,0 5,1 Theorem 1 in Erdos 1991
- ↑ 6,0 6,1 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.