Русская Википедия:Функция Кармайкла

Функция Кармайкла — теоретико-числовая функция, обозначаемая <math>\lambda(n)</math>, равная наименьшему показателю <math>m</math> такому, что

<math>a^m \equiv 1 \pmod{n}</math>

для всех целых <math>a</math>, взаимно простых с модулем <math>n</math>. Говоря языком теории групп, <math>\lambda(n)</math> — это экспонента мультипликативной группы вычетов по модулю <math>n</math>.

Приведем таблицу первых 36 значений функции <math>\lambda(n)</math> Шаблон:OEIS в сравнении со значениями функции Эйлера <math>\varphi</math>. (жирным выделены отличающиеся значения)

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
<math>\lambda(n)</math>	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
<math>\varphi(n)</math>	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 и взаимно простые с ним, <math>1^2\equiv 1 \pmod{8}; \ 3^2=9 \equiv 1 \pmod{8}; \ 5^2=25 \equiv 1 \pmod{8}; \ 7^2=49 \equiv 1 \pmod{8}</math>, значит функция Кармайкла <math>\lambda(8)</math> равна 2. Функция Эйлера <math>\varphi(8)</math> равна 4, поскольку в списке 1,3,5,7 ровно 4 числа.

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

Функция Кармайкла <math>\lambda(n)</math> от степеней нечётных простых, а также для чисел 2 и 4, равна функции Эйлера <math>\varphi(n)</math>; для степеней двойки, больших 4, она равна половине функции Эйлера:

<math>\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} </math> Функция Эйлера для степеней простых есть

<math>\varphi(p^k) = p^{k-1}(p-1).\;</math>

По основной теореме арифметики любое <math>n>1</math> может быть представлено как

где <math>p_1<p_2< \dots <p_s</math> — простые числа, а все <math>a_i>0</math>.

В общем случае, <math>\lambda(n)</math> — это наименьшее общее кратное <math>\lambda(p_i^{a_i})</math> всех точных степеней простых, входящих в разложение <math>n</math> на множители:

<math>\lambda(n) = \operatorname{lcm}[\lambda(p_1^{a_1}),\;\lambda(p_2^{a_2}),\dots,\lambda(p_s^{a_s}) ].</math>

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

Если <math>a,n</math> взаимно просты, то

<math>a^{\lambda(n)} \equiv 1 \pmod{n}</math>

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

Шаблон:Доказ1=1+2^k h</math>, то

Тогда по математической индукции мы получаем, что для всех нечётных <math>a</math> при <math>k\geqslant 3</math> верно, что <math>a^{2^{k-2}}= a^{\lambda(2^k)}\equiv 1\pmod{2^k}</math>.

Наконец, если <math>n=2^k p_1^{a_1} \dots p_s^{a_s}</math> и <math>a</math> взаимно просто с <math>n</math>, то <math> a^{\lambda(p_j^{a_j})} \equiv 1\pmod{p_j^{a_j}}</math> и <math>a^{\lambda(2^k)}\equiv 1\pmod{2^k}</math>, значит <math> a^{\lambda(n)} \equiv 1\pmod{p_j^{a_j}}</math> и <math>a^{\lambda(n)}\equiv 1\pmod{2^k}</math> и тогда <math>a^{\lambda(n)}\equiv 1\pmod{n}</math>.

Заметим также, что для любых <math>a</math> утверждение нельзя усилить: показатель <math>\lambda(n)</math> — минимальный, для которого <math>a^{\lambda(n)}\equiv 1\pmod{n}</math>. Это легко доказывается от противного.

Действительно, пусть есть простое <math>q</math> такое, что для всех <math>a</math> <math>a^{\lambda(n)/q}\equiv 1\pmod{n}</math>. Поскольку <math>\lambda(n) = \operatorname{lcm}[\lambda(p_1^{a_1}),\;\lambda(p_2^{a_2}),\dots,\lambda(p_s^{a_s}) ].</math>, то <math>q</math> делит какое-то <math>\lambda(p_i^{a_i})</math>, то есть для всех <math>a</math> <math>a^{\lambda(p_i^{a_i})/q}\equiv 1\pmod{p_i^{a_i}}</math>. Однако это противоречит тому факту, что группа <math>\mathbb{Z}_{p^k}^{\times}</math> циклична при <math>p>2</math>, а при <math>p=2</math> — противоречит тому факту, что группа <math>\mathbb{Z}_{2^k}^{\times}</math> имеет экспоненту <math>2^{k-2}</math>. }}

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

Поскольку функция Кармайкла <math>\lambda(n)</math> делит функцию Эйлера <math>\varphi(n)</math> (последовательность их частных см. в Шаблон:OEIS), теорема Кармайкла является более сильным результатом, чем классическая теорема Эйлера. Ясно, что теорема Кармайкла связана с теоремой Эйлера, потому что экспонента конечной абелевой группы всегда делит порядок группы. Функции Кармайкла и Эйлера отличаются уже при небольших аргументах: <math>\lambda(15)=4</math>, но <math>\varphi(15)=8</math>, они отличаются всегда, когда группа вычетов по модулю <math>n</math> не имеет образующей (см. последовательность Шаблон:OEIS2C).

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

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

Делимость

<math> a|b \Rightarrow \lambda(a)|\lambda(b) </math>

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

Для любых натуральных <math>a, b</math> верно, что

<math>\lambda(\mathrm{lcm}(a,b)) = \mathrm{lcm}( \lambda(a), \lambda(b) )</math>.

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

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

Если <math>a,n</math> взаимно просты и <math>m</math> — показатель числа <math>a</math> по модулю <math>n</math>, то

<math>m | \lambda(n) </math> .

Другими словами, порядок примитивного корня из единицы в кольце вычетов по модулю <math>n</math> делит <math> \lambda(n) </math>. В рамках теории групп это утверждение — простое следствие из определения экспоненты группы.

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

Если для <math>n</math> обозначить <math>x_{\max}</math> наибольший показатель простых чисел в каноническом разложении <math>n</math>, то тогда для всех <math>a</math> (включая не взаимно простые с <math>n</math>) и всех <math>k \geqslant x_{\max}</math> выполняется

<math>a^k \equiv a^{k+\lambda(n)} \pmod n</math>

В частности, для <math>n</math> свободного от квадратов <math>n</math> (для него <math>x_{\max} = 1</math>), для всех <math>a</math>

<math>a \equiv a^{\lambda(n)+1} \pmod n </math>

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

Для любого <math>x>16</math> и константы <math>B</math>:

<math>\frac{1}{x} \sum\limits_{n \leq x} \lambda (n) = \frac{x}{\ln x} e^{B (1+o(1)) \ln\ln x / (\ln\ln\ln x) }</math>^[1]^[2].

Здесь

<math>B = e^{-\gamma} \prod_p \left({1 - \frac{1}{(p-1)^2(p+1)}}\right) \approx 0.34537 \ . </math>

Для любого <math>N</math> и для всех <math>n\leqslant N</math>, за исключением <math>o(N)</math> чисел верно, что:

<math>\lambda(n) = n / (\ln n)^{\ln\ln\ln n + A + o(1)}</math>

где <math>A</math> — это постоянная^[2]^[3],

<math>A = -1 + \sum\limits_p \frac{\ln p}{(p-1)^2} \approx 0.2269688 \ . </math>

Оценки снизу

Для достаточно больших <math>N</math> и для любых <math>\Delta \geq \ln^3\ln N</math> существует как минимум

<math>Ne^{-0.69\sqrt[3]{\Delta\ln\Delta}}</math>

натуральных <math>n \leq N</math> таких, что <math>\lambda(n) \leqslant ne^{-\Delta}</math>^[4].

Для любой последовательности натуральных чисел <math>n_1<n_2<n_3<\cdots</math>, любой константы <math>0<c<1/\ln2</math> и для достаточно большого <math>i</math>:

<math>\lambda(n_i) > (\ln n_i)^{c\ln\ln\ln n_i}</math>^[5]^[6].

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

Для постоянного <math>c</math> и достаточно большого положительного <math>A</math> существует целое <math>n>A</math> такое, что <math>\lambda(n)<(\ln A)^{c\ln\ln\ln A}</math>^[6]. Более того, такое <math>n</math> имеет вид

<math>n=\prod\limits_{(q-1)|m, \ q \text{ is prime}}q</math>

при некотором <math>m<(\ln A)^{c\ln\ln\ln A}</math>, свободном от квадратов^[5].

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

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

где <math>\eta = 1-(1+\ln \ln 2)/\ln 2=0.08607\dots</math>^[7]

См. также

Примечания

Шаблон:Примечания

Литература

Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. (гл. 11 п.2)
Шаблон:Статья
Шаблон:Статья
Шаблон:Книга
Шаблон:Книга

↑ Theorem 3 in Erdos (1991)
↑ ^2,0 ^2,1 Sandor & Crstici (2004) p.194
↑ Theorem 2 in Erdos (1991)
↑ Theorem 5 in Friedlander (2001)
↑ ^5,0 ^5,1 Theorem 1 in Erdos 1991
↑ ^6,0 ^6,1 Sandor & Crstici (2004) p.193
↑ Шаблон:Cite arxiv

[1] Theorem 3 in Erdos (1991)

[HBII194-2] 2,0 ^2,1 Sandor & Crstici (2004) p.194

[3] Theorem 2 in Erdos (1991)

[4] Theorem 5 in Friedlander (2001)

[Theorem_1_in_Erdos_1991-5] 5,0 ^5,1 Theorem 1 in Erdos 1991

[HBII193-6] 6,0 ^6,1 Sandor & Crstici (2004) p.193

[7] Шаблон:Cite arxiv

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.