Лучшие вопросы
Таймлайн
Чат
Перспективы

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

арифметическая функция Из Википедии, свободной энциклопедии

Remove ads

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

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

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

Подробнее , ...
Remove ads

Пример

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

Remove ads

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

Суммиров вкратце
Перспектива

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

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

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

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

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

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

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

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

Remove ads

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

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

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

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

Суммиров вкратце
Перспектива

Делимость

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

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

.

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

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

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

.

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

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

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

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

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

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

[1][2].

Здесь

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

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

Оценки снизу

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

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

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

[5][6].

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

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

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

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

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

где [7]

Remove ads

См. также

Примечания

Литература

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads