Реклама на сайте (разместить):



Реклама и пожертвования позволяют нам быть независимыми!

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

Материал из Википедии
Перейти к: навигация, поиск

Функция Кармайкла — теоретико-числовая функция, обозначаемая \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 p p^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) ).

Это сразу получается из определения функции Кармайкла.

Примитивные корни m-й степени из единицы[править]

Если a,n взаимно просты и m — такой наименьший показатель, что a^m \equiv 1 \pmod{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/\ln2 и для достаточно большого 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]

См. также[править]

Примечания[править]

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

Литература[править]

  • Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. (гл. 11 п.2)
  • (1991) «Carmichael's lambda function». Acta Arithmetica 58: 363–385. ISSN 0065-1036.
  • (2001) «Period of the power generator and small values of the Carmichael function». Mathematics of Computation 70: 1591–1605, 1803–1806. DOI:10.1090/s0025-5718-00-01282-5. ISSN 0025-5718.
  • Handbook of number theory II. — Dordrecht: Kluwer Academic, 2004. — P. 32–36,193–195. — ISBN 1-4020-2546-7.
  • Carmichael, R. D. The Theory of Numbers. — Nabu Press. — ISBN 1144400341.
Статью можно улучшить?
✍ Редактировать 💸 Спонсировать 🔔 Подписаться 📩 Переслать 💬 Обсудить
Позвать друзей