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

Функция Кармайкла — теоретико-числовая функция, обозначаемая , равная наименьшему показателю  такому, что
 
для всех целых , взаимно простых с модулем . Говоря языком теории групп,  — это экспонента мультипликативной группы вычетов по модулю .

Приведем таблицу первых 36 значений функции   в сравнении со значениями функции Эйлера . (жирным выделены отличающиеся значения)

Пример 
1,3,5,7 — все числа, меньшие 8 и взаимно простые с ним, , значит функция Кармайкла  равна 2. Функция Эйлера  равна 4, поскольку в списке 1,3,5,7 ровно 4 числа.

Теорема Кармайкла 
Функция Кармайкла  от степеней нечётных простых, а также для чисел 2 и 4, равна функции Эйлера ; для степеней двойки, больших 4, она равна половине функции Эйлера:

 
Функция Эйлера для степеней простых есть
 

По основной теореме арифметики любое  может быть представлено как
 
где  — простые числа, а все .

В общем случае,  — это наименьшее общее кратное  всех точных степеней простых, входящих в разложение  на множители:
 

 Теорема Кармайкла
Если  взаимно просты, то
 

Иначе говоря, теорема Кармайкла утверждает, что определенная через формулу выше функция действительно удовлетворяет определению функции Кармайкла. Эта теорема может быть доказана с помощью первообразных корней и китайской теоремы об остатках.

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

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

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

Делимость

Функция Кармайкла от НОК 
Для любых натуральных  верно, что
 .
Это сразу получается из определения функции Кармайкла.

Примитивные корни из единицы 
Если  взаимно просты и  — показатель числа  по модулю , то
  .
Другими словами, порядок примитивного корня из единицы в кольце вычетов по модулю  делит . В рамках теории групп это утверждение — простое следствие из определения экспоненты группы.

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

 

В частности, для  свободного от квадратов  (для него ), для всех

Средние и типичные значения 
Для любого  и константы :

 .

Здесь
 

Для любого  и для всех , за исключением  чисел верно, что:
 
где  — это постоянная,

Оценки снизу 
Для достаточно больших  и для любых  существует как минимум
 
натуральных  таких, что .

Для любой последовательности натуральных чисел , любой константы  и для достаточно большого :
 .

Небольшие значения 
Для постоянного  и достаточно большого положительного  существует целое  такое, что .
Более того, такое  имеет вид
 
при некотором , свободном от квадратов.

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

См. также 
 Число Кармайкла
 Кармайкл, Роберт

Примечания

Литература 
 Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. (гл. 11 п.2)
 
 
 
 

Арифметика
Арифметические функции
Делимость и остатки
Дискретная математика
Модульная арифметика
Функции