Функция Кармайкла — теоретико-числовая функция, обозначаемая
λ(n), равная наименьшему показателю
m такому, что
am≡1(modn)
для всех целых
a, взаимно простых с модулем
n. Говоря языком теории
групп,
λ(n) — это экспонента мультипликативной группы вычетов
по модулю
n.
Приведем таблицу первых 36 значений функции
λ(n) в сравнении со
значениями функции Эйлера
φ. (жирным выделены отличающиеся
значения)
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) | 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) | 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 и взаимно простые с ним,
12≡1(mod8); 32=9≡1(mod8); 52=25≡1(mod8); 72=49≡1(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)=pk−1(p−1).
По основной теореме арифметики любое
n>1 может быть представлено как
n=pa11pa22…pass
где $p_1
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}Иначеговоря,теоремаКармайклаутверждает,чтоопределеннаячерезформулувышефункциядействительноудовлетворяетопределениюфункцииКармайкла.Этатеоремаможетбытьдоказанаспомощьюпервообразныхкорнейикитайскойтеоремыобостатках. =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) и всех k⩾xmax выполняется
ak≡ak+λ(n)(modn)
В частности, для n свободного от квадратов n (для него
xmax=1), для всех a
a≡aλ(n)+1(modn)
Средние и типичные
значения
Для любого x>16 и константы B:
1x∑n≤xλ(n)=xlnxeB(1+o(1))lnlnx/(lnlnlnx).
Здесь
B=e−γ∏p(1−1(p−1)2(p+1))≈0.34537 .
Для любого N и для всех n⩽N, за исключением o(N) чисел
верно, что:
λ(n)=n/(lnn)lnlnlnn+A+o(1)
где A — это постоянная,
A=−1+∑plnp(p−1)2≈0.2269688 .
Оценки
снизу
Для достаточно больших N и для любых Δ≥ln3lnN
существует как минимум
Ne−0.69ΔlnΔ√3
натуральных n≤N таких, что λ(n)⩽ne−Δ.
Для любой последовательности натуральных чисел $n_1
λ(ni)>(lnni)clnlnlnni.
Небольшие
значения
Для постоянного c и достаточно большого положительного A существует
целое n>A такое, что λ(n)<(lnA)clnlnlnA. Более того,
такое n имеет вид
n=∏(q−1)|m, q is primeq
при некотором m<(lnA)clnlnlnA, свободном от квадратов.
Множество значений функции
Кармайкла
Множество значений функции Кармайкла, не превосходящих x, имеет
мощность
xlnη+o(1)x ,
где η=1−(1+lnln2)/ln2=0.08607…