Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js

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

Функция Кармайкла — теоретико-числовая функция, обозначаемаяλ(n), равная наименьшему показателю m такому, что

am1(modn)
 для всех целых a, взаимно простых с модулем n. Говоря языком теориигрупп, λ(n) — это экспонента мультипликативной группы вычетовпо модулю n.
 Приведем таблицу первых 36 значений функции λ(n) в сравнении созначениями функции Эйлера φ. (жирным выделены отличающиесязначения)
n123456789101112131415161718192021222324252627282930313233343536
λ(n)11224262641021264416618461022220121862843081016126
φ(n)112242646410412688166188121022820121812288301620162412

Пример


 1,3,5,7 — все числа, меньшие 8 и взаимно простые с ним,121(mod8); 32=91(mod8); 52=251(mod8); 72=491(mod8),значит функция Кармайкла λ(8) равна 2. Функция Эйлераφ(8) равна 4, поскольку в списке 1,3,5,7 ровно 4 числа.

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


 Функция Кармайкла λ(n) от степеней нечётных простых, а также длячисел 2 и 4, равна функции Эйлера φ(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)=pk1(p1).
 По основной теореме арифметики любое n>1 может быть представлено как

n=pa11pa22pass
 где $p_10.  В общем случае, \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}  Иначе говоря, теорема Кармайкла утверждает, что определенная черезформулу выше функция действительно удовлетворяет определению функцииКармайкла. Эта теорема может быть доказана с помощью первообразныхкорней и китайской теоремы об остатках.  =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 такое, что для всех aa^{\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}), то есть для всех aa^{\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) (последовательность их частных см. в ), теорема Кармайклаявляется более сильным результатом, чем классическая теорема Эйлера.Ясно, что теорема Кармайкла связана с теоремой Эйлера, потому чтоэкспонента конечной абелевой группы всегда делит порядок группы. ФункцииКармайкла и Эйлера отличаются уже при небольших аргументах:\lambda(15)=4, но \varphi(15)=8, они отличаются всегда, когда группавычетов по модулю n не имеет образующей (см. последовательность ).
 Малая теорема Ферма — это частный случай теоремы Эйлера, в котороммодуль n — это простое число. Теорема Кармайкла для простых модулейдает то же утверждение, поскольку группа вычетов по простому модулюявляется цикличной, то есть её порядок и экспонента совпадают.

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


Делимость



a|b \Rightarrow \lambda(a)|\lambda(b)

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


 Для любых натуральных a, b верно, что

\lambda(\mathrm{lcm}(a,b)) = \mathrm{lcm}( \lambda(a), \lambda(b) ).
 Это сразу получается из определения функции Кармайкла.

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


 Если a,n взаимно просты и m — показатель числа a по модулю 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) }.
 Здесь

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 — это постоянная,

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}.
 Для любой последовательности натуральных чисел $n_1
\lambda(n_i) > (\ln n_i)^{c\ln\ln\ln n_i}.

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


 Для постоянного c и достаточно большого положительного A существуетцелое n>A такое, что \lambda(n)<(\ln A)^{c\ln\ln\ln A}. Более того,такое n имеет вид

n=\prod\limits_{(q-1)|m, \ q \text{ is prime}}q
 при некотором m<(\ln A)^{c\ln\ln\ln A}, свободном от квадратов.

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


 Множество значений функции Кармайкла, не превосходящих x, имеетмощность

\frac{x}{\ln^{\eta+o(1)}x} \ ,
 где \eta = 1-(1+\ln \ln 2)/\ln 2=0.08607\dots