ПОИВС | Функция Кармайкла

Функция Кармайкла — теоретико-числовая функция, обозначаемая

λ(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_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

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}) ].

\lambda(p_i^{a_i})

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}$. \}\}

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

Поскольку функция Кармайкла

делит функцию Эйлера

(последовательность их частных см. в ), теорема Кармайкла является более сильным результатом, чем классическая теорема Эйлера. Ясно, что теорема Кармайкла связана с теоремой Эйлера, потому что экспонента конечной абелевой группы всегда делит порядок группы. Функции Кармайкла и Эйлера отличаются уже при небольших аргументах:

, но

, они отличаются всегда, когда группа вычетов по модулю

не имеет образующей (см. последовательность ).
Малая теорема Ферма — это частный случай теоремы Эйлера, в котором модуль

— это простое число. Теорема Кармайкла для простых модулей дает то же утверждение, поскольку группа вычетов по простому модулю является цикличной, то есть её порядок и экспонента совпадают.

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

Делимость

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

Для любых натуральных

верно, что

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

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

Если

взаимно просты и

— показатель числа

по модулю

, то

.
Другими словами, порядок примитивного корня из единицы в кольце вычетов по модулю

делит

. В рамках теории групп это утверждение — простое следствие из определения экспоненты группы.

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

Если для

обозначить

наибольший показатель простых чисел в каноническом разложении

, то тогда для всех

(включая не взаимно простые с

) и всех

выполняется

В частности, для

свободного от квадратов

(для него

), для всех

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

Для любого

и константы

.
Здесь

Для любого

и для всех

, за исключением

чисел верно, что:

где

— это постоянная,

Оценки снизу

Для достаточно больших

и для любых

существует как минимум

натуральных

таких, что

.
Для любой последовательности натуральных чисел $n_1

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

Для постоянного

и достаточно большого положительного

существует целое

такое, что

. Более того, такое

имеет вид

при некотором

, свободном от квадратов.

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

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

, имеет мощность

где