Функция Кармайкла — теоретико-числовая функция, обозначаемая
, равная наименьшему показателю
такому, что
![{\displaystyle a^{m}\equiv 1{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6295499efc8f39a0cd7ec690788edcb794eb2bde)
для всех целых
, взаимно простых с модулем
. Говоря языком теории групп,
— это
![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
.
Приведем таблицу первых 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, она равна половине функции Эйлера:
![{\displaystyle \lambda (n)={\begin{cases}{\frac {1}{2}}\varphi (n),&{\text{если }}n=2^{k},k\geqslant 3,{\text{ т.е. }}n=8,16,32,64,128,256,\,\dots \\\;\;\varphi (n),&{\text{если }}n\in \{2,4\}\;{\text{или}}\;n=p^{k},\;p\in \mathbb {P} ,\;p>2,\;{\text{ т.е. }}\;n=2,3^{k},4,5^{k},7^{k},11^{k},13^{k},17^{k},\,\dots \end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8436d79781211e9b13cc11318e0ae35023b55015)
Функция Эйлера для степеней простых есть
![{\displaystyle \varphi (p^{k})=p^{k-1}(p-1).\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2cf77fdf0fa9ea5530a76ed7575ba1e20d7b5c6a)
По основной теореме арифметики любое
может быть представлено как
![{\displaystyle n=p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{s}^{a_{s}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09547f730b5ff87f3ee4b193ec55d3d3fc82e90e)
где
— простые числа, а все
.
В общем случае,
— это наименьшее общее кратное
всех точных степеней простых, входящих в разложение
на множители:
![{\displaystyle \lambda (n)=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{s}^{a_{s}})].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99a12e2f1cef0c835a47ac956fe318fc8b6980c9)
- Теорема Кармайкла
Если
взаимно просты, то
![{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e475506bcb72caae57599e0ccafa7efe023be9c)
Иначе говоря, теорема Кармайкла утверждает, что определенная через формулу выше функция действительно удовлетворяет определению функции Кармайкла. Эта теорема может быть доказана с помощью первообразных корней и китайской теоремы об остатках.
Докажем сначала, что для всех
взаимно простых с
выполняется
.
По малой теореме Ферма для любого простого модуля
и любого
, взаимно простого с модулем имеем
.
Если
, то
Тогда по методу математической индукции мы получаем, что для всех
.
Для модуля 2 соотношение несколько сильнее:
Если
нечётно, то
.
Тогда
.
Далее, если
, то
Тогда по математической индукции мы получаем, что для всех нечётных
при
верно, что
.
Наконец, если
и
взаимно просто с
, то
и
, значит
и
и тогда
.
Заметим также, что для любых
утверждение нельзя усилить: показатель
— минимальный, для которого
. Это легко доказывается от противного.
Действительно, пусть есть простое
такое, что для всех
. Поскольку
, то
делит какое-то
, то есть для всех
. Однако это противоречит тому факту, что группа
циклична при
, а при
— противоречит тому факту, что группа
имеет экспоненту
.
■
Связь теорем Кармайкла, Эйлера и Ферма
Поскольку функция Кармайкла
делит функцию Эйлера
(последовательность их частных см. в последовательность
всегда делит порядок группы. Функции Кармайкла и Эйлера отличаются уже при небольших аргументах:
![{\displaystyle \lambda (15)=4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bef2a7f2e591e1f49fda248552395abcd44ab7b6)
, но
![{\displaystyle \varphi (15)=8}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f9acc5b0eaad3ad3767bc8624a97af487e8ad32)
, они отличаются всегда, когда группа вычетов по модулю
![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
не имеет образующей (см. последовательность
A033949).
Малая теорема Ферма — это частный случай теоремы Эйлера, в котором модуль
— это простое число. Теорема Кармайкла для простых модулей дает то же утверждение, поскольку группа вычетов по простому модулю является цикличной, то есть её порядок и экспонента совпадают.
Свойства функции Кармайкла
Делимость
![{\displaystyle a|b\Rightarrow \lambda (a)|\lambda (b)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9161360d6268fa383e280ff4feb3fcad5662fe3a)
Функция Кармайкла от НОК
Для любых натуральных
верно, что
.
Это сразу получается из определения функции Кармайкла.
Примитивные корни из единицы
Если
взаимно просты и
—
показатель
числа
![{\displaystyle a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc)
по модулю
![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
, то
.
Другими словами, порядок примитивного корня из единицы в кольце вычетов по модулю
делит
. В рамках теории групп это утверждение — простое следствие из определения экспоненты группы.
Длина цикла экспоненты
Если для
обозначить
наибольший показатель простых чисел в каноническом разложении
, то тогда для всех
(включая не взаимно простые с
) и всех
выполняется
![{\displaystyle a^{k}\equiv a^{k+\lambda (n)}{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c483a1c6763ae488eba6f282f48918b715e6168a)
В частности, для
свободного от квадратов
(для него
), для всех
![{\displaystyle a\equiv a^{\lambda (n)+1}{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/332a904f1fca79bbc214bc8039833821c3f47cdc)
Средние и типичные значения
Для любого
и константы
:
[1][2].
Здесь
![{\displaystyle B=e^{-\gamma }\prod _{p}\left({1-{\frac {1}{(p-1)^{2}(p+1)}}}\right)\approx 0.34537\ .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/718bbbac81eb8c753f2e44c27379acbecd62e275)
Для любого
и для всех
, за исключением
чисел верно, что:
![{\displaystyle \lambda (n)=n/(\ln n)^{\ln \ln \ln n+A+o(1)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4697d152f565d9de2bbf7aed9a0dac64141f677f)
где
— это постоянная[2][3],
![{\displaystyle A=-1+\sum \limits _{p}{\frac {\ln p}{(p-1)^{2}}}\approx 0.2269688\ .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07bd8266d8a0b0a41514973210607d64aa4c0bb3)
Оценки снизу
Для достаточно больших
и для любых
существует как минимум
![{\displaystyle Ne^{-0.69{\sqrt[{3}]{\Delta \ln \Delta }}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/488adb2234084f7f389e5277af2e404fd59b814f)
натуральных
таких, что
[4].
Для любой последовательности натуральных чисел
, любой константы
и для достаточно большого
:
[5][6].
Небольшие значения
Для постоянного
и достаточно большого положительного
существует целое
такое, что
[6].
Более того, такое
имеет вид
![{\displaystyle n=\prod \limits _{(q-1)|m,\ q{\text{ is prime}}}q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b34b073fdeedb4f3b85a80d3d001b2414aff99d)
при некотором
, свободном от квадратов[5].
Множество значений функции Кармайкла
Множество значений функции Кармайкла, не превосходящих
, имеет мощность
![{\displaystyle {\frac {x}{\ln ^{\eta +o(1)}x}}\ ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0222c9d741aec7fe72f4e341a97a21b631252404)
где
[7]
См. также
Примечания
- ↑ Theorem 3 in Erdos (1991)
- ↑ 1 2 Sandor & Crstici (2004) p.194
- ↑ Theorem 2 in Erdos (1991)
- ↑ Theorem 5 in Friedlander (2001)
- ↑ 1 2 Theorem 1 in Erdos 1991
- ↑ 1 2 Sandor & Crstici (2004) p.193
- ↑ Ford, Kevin; Luca, Florian; Pomerance, Carl (27 August 2014). "The image of Carmichael's ?-function". arXiv:1408.6506 [math.NT].
Литература