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

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

Cвойства

Кармайкловы числа имеют по меньшей мере три простых положительных множителя.

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

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

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

для некоторой константы . При этом также доказано,^[1] что существует бесконечно много чисел Кармайкла, то есть, .

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

Интересные факты

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

Примечания