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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Приведем таблицу первых 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
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, она равна половине функции Эйлера:

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

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

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

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

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

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

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

Связь теорем Кармайкла, Эйлера и Ферма[править | править код]

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

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

Свойства функции Кармайкла[править | править код]

Делимость[править | править код]

Функция Кармайкла от НОК[править | править код]

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

.

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

Примитивные корни из единицы[править | править код]

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

.

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

Длина цикла экспоненты[править | править код]

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

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

Средние и типичные значения[править | править код]

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

[1][2].

Здесь

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

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

Оценки снизу[править | править код]

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

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

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

[5][6].

Небольшие значения[править | править код]

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

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

Множество значений функции Кармайкла[править | править код]

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

где [7]

См. также[править | править код]

Примечания[править | править код]

  1. Theorem 3 in Erdos (1991)
  2. 1 2 Sandor & Crstici (2004) p.194
  3. Theorem 2 in Erdos (1991)
  4. Theorem 5 in Friedlander (2001)
  5. 1 2 Theorem 1 in Erdos 1991
  6. 1 2 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] 

Литература[править | править код]

  • Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. (гл. 11 п.2)
  • Erdos, Paul; Pomerance, Carl; Schmutz, Eric (1991). “Carmichael's lambda function”. Acta Arithmetica. 58: 363—385. ISSN 0065-1036. MR 1121092. Zbl 0734.11047.
  • Friedlander, John B.; Pomerance, Carl; Shparlinski, Igor E. (2001). “Period of the power generator and small values of the Carmichael function”. Mathematics of Computation. 70 (236): 1591—1605, 1803—1806. DOI:10.1090/s0025-5718-00-01282-5. ISSN 0025-5718. MR 1836921. Zbl 1029.11043.
  • Sandor, Jozsef. Handbook of number theory II / Jozsef Sandor, Borislav Crstici. — Dordrecht : Kluwer Academic, 2004. — P. 32–36,193–195. — ISBN 1-4020-2546-7.
  • Carmichael, R. D. The Theory of Numbers. — Nabu Press. — ISBN 1144400341.