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

Функция Кармайкла — теоретико-числовая функция, обозначаемая λ(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=p1a1p2a2psas
  где $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\^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}.Наконец,если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}$. \}\}

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


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

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


Делимость



a|bλ(a)|λ(b)

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


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

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

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


 Если a,n взаимно просты и m — показатель числа a по модулю n, то

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

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


 Если для n обозначить xmax наибольший показатель простых чисел в каноническом разложении n, то тогда для всех a (включая не взаимно простые с n) и всех kxmax выполняется

akak+λ(n)(modn)
  В частности, для n свободного от квадратов n (для него xmax=1), для всех a

aaλ(n)+1(modn)

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


 Для любого x>16 и константы B:

1xnxλ(n)=xlnxeB(1+o(1))lnlnx/(lnlnlnx).
  Здесь

B=eγp(11(p1)2(p+1))0.34537 .
  Для любого N и для всех nN, за исключением o(N) чисел верно, что:

λ(n)=n/(lnn)lnlnlnn+A+o(1)
  где A — это постоянная,

A=1+plnp(p1)20.2269688 .

Оценки снизу


 Для достаточно больших N и для любых Δln3lnN существует как минимум

Ne0.69ΔlnΔ3
  натуральных nN таких, что λ(n)neΔ.
 Для любой последовательности натуральных чисел $n_1
λ(ni)>(lnni)clnlnlnni.

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


 Для постоянного c и достаточно большого положительного A существует целое n>A такое, что λ(n)<(lnA)clnlnlnA. Более того, такое n имеет вид

n=(q1)|m, q is primeq
  при некотором m<(lnA)clnlnlnA, свободном от квадратов.

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


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

xlnη+o(1)x ,
  где η=1(1+lnln2)/ln2=0.08607