Функция Кармайкла — теоретико-числовая функция, обозначаемая , равная наименьшему показателю такому, что
для всех целых , взаимно простых с модулем . Говоря языком теории групп, — это экспонента мультипликативной группы вычетов по модулю .
Приведем таблицу первых 36 значений функции в сравнении со значениями функции Эйлера . (жирным выделены отличающиеся значения)
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 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 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 и взаимно простые с ним, , значит функция Кармайкла равна 2. Функция Эйлера равна 4, поскольку в списке 1,3,5,7 ровно 4 числа.
Теорема Кармайкла Функция Кармайкла от степеней нечётных простых, а также для чисел 2 и 4, равна функции Эйлера ; для степеней двойки, больших 4, она равна половине функции Эйлера:
Функция Эйлера для степеней простых есть
По основной теореме арифметики любое может быть представлено как
где — простые числа, а все .
В общем случае, — это наименьшее общее кратное всех точных степеней простых, входящих в разложение на множители:
Теорема Кармайкла Если взаимно просты, то
Иначе говоря, теорема Кармайкла утверждает, что определенная через формулу выше функция действительно удовлетворяет определению функции Кармайкла. Эта теорема может быть доказана с помощью первообразных корней и китайской теоремы об остатках.
Связь теорем Кармайкла, Эйлера и Ферма Поскольку функция Кармайкла делит функцию Эйлера (последовательность их частных см. в ), теорема Кармайкла является более сильным результатом, чем классическая теорема Эйлера. Ясно, что теорема Кармайкла связана с теоремой Эйлера, потому что экспонента конечной абелевой группы всегда делит порядок группы. Функции Кармайкла и Эйлера отличаются уже при небольших аргументах: , но , они отличаются всегда, когда группа вычетов по модулю не имеет образующей (см. последовательность ).
Малая теорема Ферма — это частный случай теоремы Эйлера, в котором модуль — это простое число. Теорема Кармайкла для простых модулей дает то же утверждение, поскольку группа вычетов по простому модулю является цикличной, то есть её порядок и экспонента совпадают.
Свойства функции Кармайкла
Делимость
Функция Кармайкла от НОК Для любых натуральных верно, что . Это сразу получается из определения функции Кармайкла.
Примитивные корни из единицы Если взаимно просты и — показатель числа по модулю , то . Другими словами, порядок примитивного корня из единицы в кольце вычетов по модулю делит . В рамках теории групп это утверждение — простое следствие из определения экспоненты группы.
Длина цикла экспоненты Если для обозначить наибольший показатель простых чисел в каноническом разложении , то тогда для всех (включая не взаимно простые с ) и всех выполняется
В частности, для свободного от квадратов (для него ), для всех
Средние и типичные значения Для любого и константы :
Theorem 3 in Erdos (1991)Sandor & Crstici (2004) p.194.
Здесь
Для любого и для всех , за исключением чисел верно, что:
где — это постояннаяTheorem 2 in Erdos (1991),
Оценки снизу Для достаточно больших и для любых существует как минимум
натуральных таких, что Theorem 5 in Friedlander (2001).
Для любой последовательности натуральных чисел , любой константы и для достаточно большого : Theorem 1 in Erdos 1991Sandor & Crstici (2004) p.193.
Небольшие значения Для постоянного и достаточно большого положительного существует целое такое, что . Более того, такое имеет вид
при некотором , свободном от квадратов.
Множество значений функции Кармайкла Множество значений функции Кармайкла, не превосходящих , имеет мощность
где
См. также Число Кармайкла Кармайкл, Роберт
Примечания
Литература Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. (гл. 11 п.2)
Категория:Арифметика Категория:Арифметические функции Категория:Делимость и остатки Категория:Дискретная математика Категория:Модульная арифметика Категория:Функции