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

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

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

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

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
11224262641021264416618461022220121862843081016126
112242646410412688166188121022820121812288301620162412

Пример

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

Теорема Кармайкла

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

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

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

где  — простые числа, а все .

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

Теорема Кармайкла

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

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

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

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

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

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

Делимость

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

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

.

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

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

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

.

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

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

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

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

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

Для любого и константы :

[1][2].

Здесь

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

где  — это постоянная[2][3],

Оценки снизу

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

натуральных таких, что [4].

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

[5][6].

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

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

при некотором , свободном от квадратов[5].

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

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

где [7]

См. также

Примечания

  1. Theorem 3 in Erdos (1991)
  2. Sandor & Crstici (2004) p.194
  3. Theorem 2 in Erdos (1991)
  4. Theorem 5 in Friedlander (2001)
  5. Theorem 1 in Erdos 1991
  6. Sandor & Crstici (2004) p.193
  7. Ford, Kevin; Luca, Florian & Pomerance, Carl (27 August 2014), The image of Carmichael's ?-function, arΧiv:1408.6506 [math.NT]

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.