Число Кармайкла

Число Кармайкла — составное число ${\displaystyle n}$, которое удовлетворяет сравнению ${\displaystyle b^{n-1}\equiv 1{\pmod {n}}}$ для всех целых ${\displaystyle b}$, взаимно простых с ${\displaystyle n}$, другими словами — псевдопростое число по каждому основанию ${\displaystyle b}$, взаимно простому с ${\displaystyle n}$. Такие числа относительно редки, но их бесконечное число, наименьшее из них — 561; существование таких чисел делает недостаточным условие простоты малой теоремы Ферма, и не позволяет применять тест Ферма как универсальное средство проверки простоты.

Названы по имени американского математика Роберта Кармайкла.

Общие сведения

Малая теорема Ферма утверждает, что если ${\displaystyle n}$ — простое число и ${\displaystyle b}$ — целое число, не делящееся на ${\displaystyle n}$, то ${\displaystyle b^{n-1}-1}$ делится на ${\displaystyle n}$, то есть ${\displaystyle b^{n}\equiv b{\pmod {n}}}$. Числа Кармайкла являются составными, при этом для них выполняется данное соотношение. Числа Кармайкла также называют абсолютно псевдопростыми числами Ферма, так как они являются псевдопростыми числами Ферма по каждому взаимно простому с ними основанию.

Существование чисел Кармайкла делает тест простоты Ферма менее эффективным для обнаружения простых чисел, по сравнению, например, с более строгим тестом Соловея — Штрассена, который распознаёт эти числа как составные. По мере возрастания числа Кармайкла становятся более редкими. Например, в промежутке от 1 до 10^21 их содержится 20 138 200 (примерно одно на 50 триллионов чисел). Тем не менее, доказано, что существует бесконечно много чисел Кармайкла[1].

История

Первым, кто открыл числовые свойства, которые впоследствии стали характеристикой чисел Кармайкла, был Алвин Корсельт, доказавшим в 1899 году теорему о целых числах, эквивалентную условиям обращения малой теоремы Ферма, то есть для целых чисел ${\displaystyle n}$, для которых выполняется ${\displaystyle b^{n}\equiv b{\pmod {n}}}$ при любых целых ${\displaystyle b}$: составное число ${\displaystyle n}$ является числом Кармайкла тогда и только тогда, когда ${\displaystyle n}$ свободно от квадратов и для каждого простого делителя ${\displaystyle p}$ числа ${\displaystyle n}$ число ${\displaystyle p-1}$ делит число ${\displaystyle n-1}$[2].

Доказательство теоремы Корсельта[2].

Пусть, что ${\displaystyle b^{n}\equiv b{\pmod {n}}}$ для всех целых ${\displaystyle b}$. Сначала докажем, что число ${\displaystyle n}$ должно быть свободно от квадратов. Предположим, что это не так и ${\displaystyle k^{2}\mid n}$ (${\displaystyle k^{2}}$ делит ${\displaystyle n}$) для некоторого целого ${\displaystyle k>1}$. Пусть ${\displaystyle b=k}$, тогда ${\displaystyle k^{n}\equiv k{\pmod {n}}}$. Так как ${\displaystyle k^{2}\mid n}$, то это соотношение верно по модулю ${\displaystyle k^{2}}$, то есть ${\displaystyle k^{n}\equiv k{\pmod {k^{2}}}}$, что противоречит выражению ${\displaystyle k^{n}\equiv 0{\pmod {k^{2}}}}$. Таким образом, число ${\displaystyle n}$ свободно от квадратов. Пусть теперь ${\displaystyle p}$ – простой делитель числа ${\displaystyle n}$. Известно, что мультипликативная группа ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{*}}$ кольца вычетов по модулю ${\displaystyle p}$, где ${\displaystyle p}$ – простое, является циклической группой порядка ${\displaystyle p-1}$. Пусть ${\displaystyle b}$ – целое число, такое, что ${\displaystyle b{\pmod {p}}}$ – генератор группы ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{*}}$. Так как ${\displaystyle b^{n}\equiv b{\pmod {n}}}$, то имеем ${\displaystyle b^{n}\equiv b{\pmod {p}}}$, и так как ${\displaystyle b}$ и ${\displaystyle p}$ – взаимнопростые числа, то ${\displaystyle b^{n-1}\equiv 1{\pmod {p}}}$. Из того, что порядок примитивного элемента ${\displaystyle b{\pmod {p}}}$ в группе ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{*}}$ равен ${\displaystyle p-1}$, следует, что ${\displaystyle p-1\mid n-1}$.

С другой стороны, предположим, что ${\displaystyle n}$ свободно от квадратов и ${\displaystyle p-1\mid n-1}$ для любого простого ${\displaystyle p|n}$. Пусть ${\displaystyle p}$ — некоторое простое число, делящее ${\displaystyle n}$, и число ${\displaystyle b}$ – целое.

Из малой теоремы Ферма следует, что если ${\displaystyle p}$ – простое, а ${\displaystyle b}$ – целое, то ${\displaystyle b^{k}\equiv b{\pmod {p}}}$ для любого положительного целого ${\displaystyle k}$, такого что ${\displaystyle p-1\mid k-1}$. (Пусть ${\displaystyle q\cdot (p-1)=(k-1)}$, где ${\displaystyle q}$ — положительное целое число. Так как ${\displaystyle b^{p}\equiv b\cdot b^{p-1}\equiv b{\pmod {p}},b^{p-1}\equiv 1{\pmod {p}}}$, поэтому ${\displaystyle b\cdot b^{p-1}\cdot b^{p-1}\cdot \ldots \cdot b^{p-1}\equiv b\cdot b^{q\cdot (p-1)}\equiv b\cdot b^{k-1}\equiv b^{k}\equiv b{\pmod {p}}}$)

Тогда для частного случая ${\displaystyle k=n}$ мы имеем, что ${\displaystyle b^{n}-b}$ делится на любой простой делитель числа ${\displaystyle n}$, так как ${\displaystyle n}$ свободно от квадратов, то ${\displaystyle b^{n}-b}$ делится на ${\displaystyle n}$, то есть ${\displaystyle b^{n}\equiv b{\pmod {n}}}$. Таким образом теорема Корсельта доказана.

Корсельт оставил открытым вопрос поиска составных чисел, удовлетворяющих этому критерию. В 1910 году Кармайкл сформулировал критерий, по существу совпадающий с критерием Корсельта, и дал пример составного числа ${\displaystyle n}$, для которого он выполняется — ${\displaystyle n=561}$. Это число раскладывается на простые множители как 561 = 3·11·17, и поэтому свободно от квадратов, в то время как ${\displaystyle 561-1=560}$ делится на 2, 10 и 16. После чего все контрпримеры получили наименование чисел Кармайкла.

В частности, из теоремы Корсельта следует, что все числа Кармайкла нечётны, так как любое чётное составное число, свободное от квадратов, имеет по крайней мере один нечётный простой делитель, и поэтому из делимости ${\displaystyle p-1\mid n-1}$ следует, что чётное делит нечётное, что невозможно.

В 1939 году Джон Черник доказал теорему, которая может быть использована для построения подмножества чисел Кармайкла: если ${\displaystyle 6m+1}$, ${\displaystyle 12m+1}$, ${\displaystyle 18m+1}$ — простые числа для одного натурального ${\displaystyle m}$, то их произведение ${\displaystyle M_{3}(m)=(6m+1)(12m+1)(18m+1)}$ является числом Кармайкла[2]. Это условие может быть удовлетворено, только если число ${\displaystyle m}$ заканчивается цифрами 0, 1, 5 или 6 по основанию 10, то есть ${\displaystyle m}$ сравнимо с 0 или 1 по модулю 5. Например, для ${\displaystyle m=1}$ множители равны соответственно ${\displaystyle 7}$, ${\displaystyle 13}$ и ${\displaystyle 19}$, а их произведение даёт число Кармайкла 1729.

Способ нахождения чисел Кармайкла, предложенный Черником, может быть расширен на количество множителей ${\displaystyle k\geqslant 3}$:

${\displaystyle M_{k}(m)=(6m+1)(12m+1)\prod _{i=1}^{k-2}(9\cdot 2^{i}m+1),\quad k\geqslant 3}$,

при условии, что все множители простые и ${\displaystyle m}$ делится на ${\displaystyle 2^{k-4}}$.

Гипотезу о бесконечности таких чисел высказал ещё Кармайкл в 1912 году, теорема Черника умозрительно повысила вероятность её выполнения; позднее Пал Эрдёш эвристически обосновал бесконечность чисел Кармайкла. Однако только в 1992 году[2] это утверждение было строго доказано Уильямом Алфордом, Эндрю Грэнвиллом и Карлом Померансом[1], точнее: доказано, что между 1 и достаточно большим ${\displaystyle n}$ содержится ${\displaystyle n^{2/7}}$ чисел Кармайкла.

В 1992 году Гюнтер Лё И Вольфганг Нибур предложили новый алгоритм для построения больших чисел Кармайкла: удалось найти число, получаемое перемножением 1 101 518 простых чисел; это число содержит 16 142 049 цифр[3].

Свойства

Теоремы Бигера и Дюпарка

В 1956 году Бигер доказал, что если для простых чисел ${\displaystyle p}$, ${\displaystyle q}$ и ${\displaystyle r}$ выполняется соотношение ${\displaystyle p<q<r}$ и ${\displaystyle pqr}$ — число Кармайкла, то ${\displaystyle q<2p^{2}}$ и ${\displaystyle r<p^{3}}$. Таким образом, количество чисел Кармайкла, получаемых произведением трёх простых множителей, один из которых известен, конечно.

Дюпарк позже обобщил этот результат, чтобы показать, что если ${\displaystyle n=mqr}$ — число Кармайкла, где ${\displaystyle q}$ и ${\displaystyle r}$ — простые, тогда ${\displaystyle q<2m^{2}}$ и ${\displaystyle r<m^{3}}$. Следовательно, существует не более чем конечное количество чисел Кармайкла со всеми, кроме двух, определёнными множителями.

Случай ${\displaystyle m}$ = 1 показывает, что любое кармайклово число содержит как минимум 3 простых множителя, к этому выводу впервые пришёл сам Кармайкл.

Разложения на простые множители

Разложения первых нескольких чисел Кармайкла на простые множители таковы:

${\displaystyle {\begin{aligned}561=3\cdot 11\cdot 17&\qquad (2\mid 560;10\mid 560;16\mid 560),\\1105=5\cdot 13\cdot 17&\qquad (4\mid 1104;12\mid 1104;16\mid 1104),\\1729=7\cdot 13\cdot 19&\qquad (6\mid 1728;12\mid 1728;18\mid 1728),\\2465=5\cdot 17\cdot 29&\qquad (4\mid 2464;16\mid 2464;28\mid 2464),\\2821=7\cdot 13\cdot 31&\qquad (6\mid 2820;12\mid 2820;30\mid 2820),\\6601=7\cdot 23\cdot 41&\qquad (6\mid 6600;22\mid 6600;40\mid 6600),\\8911=7\cdot 19\cdot 67&\qquad (6\mid 8910;18\mid 8910;66\mid 8910).\end{aligned}}}$

Кармайкловы числа имеют по меньшей мере три простых положительных множителя. Первые кармайкловы числа с ${\displaystyle k=3,4,5,\ldots }$ простыми множителями[4]:

k
3	${\displaystyle 561=3\cdot 11\cdot 17}$
4	${\displaystyle 41041=7\cdot 11\cdot 13\cdot 41}$
5	${\displaystyle 825265=5\cdot 7\cdot 17\cdot 19\cdot 73}$
6	${\displaystyle 321197185=5\cdot 19\cdot 23\cdot 29\cdot 37\cdot 137}$
7	${\displaystyle 5394826801=7\cdot 13\cdot 17\cdot 23\cdot 31\cdot 67\cdot 73}$
8	${\displaystyle 232250619601=7\cdot 11\cdot 13\cdot 17\cdot 31\cdot 37\cdot 73\cdot 163}$
9	${\displaystyle 9746347772161=7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 31\cdot 37\cdot 41\cdot 641}$

Первые кармайкловы числа с четырьмя простыми множителями[5]:

i
1	${\displaystyle 41041=7\cdot 11\cdot 13\cdot 41}$
2	${\displaystyle 62745=3\cdot 5\cdot 47\cdot 89}$
3	${\displaystyle 63973=7\cdot 13\cdot 19\cdot 37}$
4	${\displaystyle 75361=11\cdot 13\cdot 17\cdot 31}$
5	${\displaystyle 101101=7\cdot 11\cdot 13\cdot 101}$
6	${\displaystyle 126217=7\cdot 13\cdot 19\cdot 73}$
7	${\displaystyle 172081=7\cdot 13\cdot 31\cdot 61}$
8	${\displaystyle 188461=7\cdot 13\cdot 19\cdot 109}$
9	${\displaystyle 278545=5\cdot 17\cdot 29\cdot 113}$
10	${\displaystyle 340561=13\cdot 17\cdot 23\cdot 67}$

Распределение

Следующая таблица показывает количество ${\displaystyle C(X)}$ чисел Кармайкла меньше или равных числу ${\displaystyle X}$, которое задаётся как степень ${\displaystyle n}$ десяти:[6]

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
${\displaystyle C(10^{n})}$	0	0	1	7	16	43	105	255	646	1547	3605	8241	19279	44706	105212	246683

В 1953 году Вальтер Кнёдель доказал, что:

${\displaystyle C(X)<X\exp \left({-k_{1}\left(\log X\log \log X\right)^{\frac {1}{2}}}\right)}$

для некоторой константы ${\displaystyle k_{1}}$.

Пусть ${\displaystyle C(X)}$ обозначает количество чисел Кармайкла, меньших ${\displaystyle X}$. Эрдёш доказал в 1956 году, что

${\displaystyle C(X)<X\exp {\frac {-k_{2}\log {X}\log {\log {\log {X}}}}{\log {\log {X}}}}}$

для некоторой константы ${\displaystyle k_{2}}$. При этом также доказано[1], что существует бесконечно много чисел Кармайкла, то есть, ${\displaystyle \lim _{X\to \infty }C(X)=\infty }$.

В следующей таблице приведены приближённые минимальные значения константы k для значений X = 10^n при разных n:

${\displaystyle n}$	4	6	8	10	12	14	16	18	20	21
k	2,19547	1,97946	1,90495	1,86870	1,86377	1,86293	1,86406	1,86522	1,86598	1,86619

Редкие свойства отдельных чисел

Второе кармайклово число (1105) может быть представлено как сумма двух квадратов большим количеством способов, чем любое меньшее число.

Третье кармайклово число (1729) является числом Рамануджана — Харди (наименьшее число, представимое в виде суммы двух кубов двумя способами).

Примечания

1. W. R. Alford, A. Granville, C. Pomerance. There are Infinitely Many Carmichael Numbers (англ.) // Annals of Mathematics : journal. — 1994. — Vol. 139. — P. 703—722. — doi:10.2307/2118576. Архивировано 4 марта 2005 года.
2. C. Pomerance. Carmichael numbers (неопр.) // Nieuw Arch. Wisk.. — 1993. — С. 199—209. Архивировано 7 февраля 2015 года.
3. G Löh, W. Niebuhr. A new algorithm for constructing large Carmichael numbers (англ.) // Math. Comp.^[англ.] : journal. — 1996. — Vol. 65, no. 214. — P. 823—836. Архивировано 7 февраля 2015 года.
4. последовательность A006931 в OEIS
5. последовательность A074379 в OEIS
6. Richard Pinch. "The Carmichael numbers up to 10^21"  (неопр.) (2007). Дата обращения: 9 февраля 2015. Архивировано 8 августа 2014 года.