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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Делимость

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

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

.

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

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

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

.

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

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

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

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

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

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

.

Здесь

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

где — это постоянная ,

Оценки снизу

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

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

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

.

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

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

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

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

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

где

См. также

Примечания

  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". arXiv : [ ].

Литература

  • Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. (гл. 11 п.2)
  • (англ.) ; (англ.) ; Schmutz, Eric. Carmichael's lambda function (неопр.) // (англ.) . — 1991. — Т. 58 . — С. 363—385 . — ISSN .
  • (англ.) ; Pomerance, Carl; Shparlinski, Igor E. Period of the power generator and small values of the Carmichael function (англ.) // (англ.) : journal. — 2001. — Vol. 70 . — P. 1591—1605, 1803—1806 . — ISSN . — doi : .
  • Sandor, Jozsef; Crstici, Borislav. Handbook of number theory II (неопр.) . — Dordrecht: Kluwer Academic , 2004. — С. 32—36,193—195. — ISBN 1-4020-2546-7 .
  • Carmichael, R. D. (неопр.) . — Nabu Press. — ISBN 1144400341 .
Источник —

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