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

В теории чисел числом Кармайкла (кармайкловым числом) называется всякое составное число n, которое удовлетворяют сравнению $b^{n-1}\equiv 1\pmod{n}$ для всех целых b, взаимно простых с n. Другими словами, числом Кармайкла называется составное число n, которое является псевдопростым числом по каждому основанию b, взаимно простому с n.

Своё название числа Кармайкла получили в честь Роберта Кармайкла.

Критерий Корсельта

Эквивалентное определение чисел Кармайкла дает критерий Корсельта.

Теорема (Корсельт, 1899): Составное число n является кармайкловым тогда и только тогда, когда n свободно от квадратов и для каждого простого делителя p числа n число p−1 делит число n−1.

В частности, из теоремы Корсельта следует, что все числа Кармайкла нечётны, так как любое чётное составное число, свободное от квадратов, имеет по крайней мере один нечётный простой делитель, и поэтому из делимости p−1 | n−1 следует, что чётное делит нечётное, что невозможно.

Корсельт был первым, кто заметил это свойство, но он так и не смог найти какие-либо примеры. В 1910 году Кармайкл нашел первое и наименьшее такое число, 561.

Примеры

Последовательность чисел Кармайкла начинается так:

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, … (последовательность A002997 в OEIS)

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

$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).$

Cвойства

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

Кармайкловы числа имеют по меньшей мере три простых положительных множителя. Первые Кармайкловы числа с $k = 3, 4, 5, \ldots$ простыми множителями (последовательность A006931 в OEIS):

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

Первые кармайкловы числа с четырьмя простыми множителями (последовательность A074379 в OEIS):

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

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

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

$C(X) < X \exp{\frac{-k \log{X} \log{\log{\log{X}}}}{\log{\log{X}}}}$

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

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

$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 (1994). «There are Infinitely Many Carmichael Numbers». Annals of Mathematics 139: 703-722. DOI:10.2307/2118576.

Для улучшения этой статьи по математике желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.