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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории чисел числом Кармайкла (кармайкловым числом) называется всякое составное число 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).

Свойства[править | править вики-текст]

Разложения на простые множители[править | править вики-текст]

Кармайкловы числа имеют по меньшей мере три простых положительных множителя. Первые Кармайкловы числа с 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 = 10n при разных 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.