Лучшие вопросы
Таймлайн
Чат
Перспективы
Функция Кармайкла
арифметическая функция Из Википедии, свободной энциклопедии
Remove ads
Функция Кармайкла — теоретико-числовая функция, обозначаемая , равная наименьшему показателю такому, что
для всех целых , взаимно простых с модулем . Говоря языком теории групп, — это экспонента мультипликативной группы вычетов по модулю .
Приведем таблицу первых 36 значений функции последовательность A002322 в OEIS в сравнении со значениями функции Эйлера . (жирным выделены отличающиеся значения)
Remove ads
Пример
1,3,5,7 — все числа, меньшие 8 и взаимно простые с ним, , значит функция Кармайкла равна 2. Функция Эйлера равна 4, поскольку в списке 1,3,5,7 ровно 4 числа.
Remove ads
Теорема Кармайкла
Суммиров вкратце
Перспектива
Функция Кармайкла от степеней нечётных простых, а также для чисел 2 и 4, равна функции Эйлера ; для степеней двойки, больших 4, она равна половине функции Эйлера:
Функция Эйлера для степеней простых есть
По основной теореме арифметики любое может быть представлено как
где — простые числа, а все .
В общем случае, — это наименьшее общее кратное всех точных степеней простых, входящих в разложение на множители:
- Теорема Кармайкла
Если взаимно просты, то
Иначе говоря, теорема Кармайкла утверждает, что определенная через формулу выше функция действительно удовлетворяет определению функции Кармайкла. Эта теорема может быть доказана с помощью первообразных корней и китайской теоремы об остатках.
Доказательство
Докажем сначала, что для всех взаимно простых с выполняется .
По малой теореме Ферма для любого простого модуля и любого , взаимно простого с модулем имеем .
Если , то
Тогда по методу математической индукции мы получаем, что для всех .
Для модуля 2 соотношение несколько сильнее:
Если нечётно, то .
Тогда .
Далее, если , то
Тогда по математической индукции мы получаем, что для всех нечётных при верно, что .
Наконец, если и взаимно просто с , то и , значит и и тогда .
Заметим также, что для любых утверждение нельзя усилить: показатель — минимальный, для которого . Это легко доказывается от противного.
Действительно, пусть есть простое такое, что для всех . Поскольку , то делит какое-то , то есть для всех . Однако это противоречит тому факту, что группа циклична при , а при — противоречит тому факту, что группа имеет экспоненту .
Remove ads
Связь теорем Кармайкла, Эйлера и Ферма
Поскольку функция Кармайкла делит функцию Эйлера (последовательность их частных см. в последовательность A034380 в OEIS), теорема Кармайкла является более сильным результатом, чем классическая теорема Эйлера. Ясно, что теорема Кармайкла связана с теоремой Эйлера, потому что экспонента конечной абелевой группы всегда делит порядок группы. Функции Кармайкла и Эйлера отличаются уже при небольших аргументах: , но , они отличаются всегда, когда группа вычетов по модулю не имеет образующей (см. последовательность A033949).
Малая теорема Ферма — это частный случай теоремы Эйлера, в котором модуль — это простое число. Теорема Кармайкла для простых модулей дает то же утверждение, поскольку группа вычетов по простому модулю является цикличной, то есть её порядок и экспонента совпадают.
Свойства функции Кармайкла
Суммиров вкратце
Перспектива
Делимость
Функция Кармайкла от НОК
Для любых натуральных верно, что
- .
Это сразу получается из определения функции Кармайкла.
Примитивные корни из единицы
Если взаимно просты и — показатель числа по модулю , то
- .
Другими словами, порядок примитивного корня из единицы в кольце вычетов по модулю делит . В рамках теории групп это утверждение — простое следствие из определения экспоненты группы.
Длина цикла экспоненты
Если для обозначить наибольший показатель простых чисел в каноническом разложении , то тогда для всех (включая не взаимно простые с ) и всех выполняется
В частности, для свободного от квадратов (для него ), для всех
Средние и типичные значения
Для любого и константы :
Здесь
Для любого и для всех , за исключением чисел верно, что:
Оценки снизу
Для достаточно больших и для любых существует как минимум
натуральных таких, что [4].
Для любой последовательности натуральных чисел , любой константы и для достаточно большого :
Небольшие значения
Для постоянного и достаточно большого положительного существует целое такое, что [6]. Более того, такое имеет вид
при некотором , свободном от квадратов[5].
Множество значений функции Кармайкла
Множество значений функции Кармайкла, не превосходящих , имеет мощность
где [7]
Remove ads
См. также
Примечания
Литература
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads