Введение

Составное число в теории чисел

В теории чисел число Кармайкла — это составное число n, которое в модульной арифметике удовлетворяет сравнению:

для всех целых чисел b. Это сравнение также может быть выражено в виде:

для всех целых чисел, взаимно простых с n. Они бесконечны по количеству. Они представляют собой относительно редкие случаи, когда обратное утверждение к малой теореме Ферма неверно. Этот факт исключает использование малой теоремы Ферма в качестве абсолютного теста на простоту. Числа Кармайкла образуют подмножество K1 чисел Кноделя. Числа Кармайкла были названы в честь американского математика Роберта Кармайкла Николасом Бигером в 1950 году. Øystein Ore в 1948 году называл их числами с «свойством Ферма» или, сокращенно, «F-числами».

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

Альтернативное и эквивалентное определение чисел Кармайкла дается критерием Корсельта. Теорема (А. Корселт, 1899): Положительное составное число является числом Кармайкла тогда и только тогда, когда оно свободно от квадратов, и для всех простых делителей *p* числа *n* выполняется условие *p* - 1 делит *n* - 1. Из этой теоремы следует, что все числа Кармайкла нечетны, поскольку любое четное составное число, свободное от квадратов (и, следовательно, имеющее только один простой делитель – два), будет иметь хотя бы один нечетный простой делитель, и, таким образом, четное число будет делить нечетное, что является противоречием. (Нечетность чисел Кармайкла также следует из того факта, что оно является свидетелем Ферма для любого четного составного числа.) Из критерия также следует, что числа Кармайкла являются циклическими. Кроме того, следует, что не существует чисел Кармайкла, имеющих ровно два простых делителя.

Число Лукаса и Кармихала

Положительное составное число является числом Лукаса — Кармихала тогда и только тогда, когда оно свободно от квадратов, и для всех простых делителей p числа n выполняется условие p + 1 делит n + 1. Первые числа Лукаса — Кармихала: 399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095, 20705, 20999, 22847, 29315, 31535, 46079, 51359, 60059, 63503, 67199, 73535, 76751, 80189, 81719, 88559, 90287.

Квази-кармикелевское число

Квази-кармихелевы числа — это составные числа, не содержащие квадратов простых множителей (числа, свободные от квадратов), 1=n, обладающие свойством, что для каждого простого делителя 1=p числа 1=n, величина 1=p + b делит 1=n + b нацело, где 1=b — любое целое число, отличное от нуля. Если 1=b = 1, то это числа Кармайкла, а если 1=b = -1, то это числа Лукаса — Кармайкла. Первые квази-кармихелевы числа:
35, 77, 143, 165, 187, 209, 221, 231, 247, 273, 299, 323, 357, 391, 399, 437, 493, 527, 561, 589, 598, 713, 715, 899, 935, 943, 989, 1015, 1073, 1105, 1147, 1189, 1247, 1271, 1295, 1333, 1517, 1537, 1547, 1591, 1595, 1705, 1729,

Число колен

Число Кноделя для заданного положительного целого числа n — это составное число m, обладающее свойством, что для каждого 1 ≤ i < m, взаимно простого с m, выполняется 1 ≤ i^(m - n) ≡ 1 (mod m). Случай n = 1 — это числа Кармайкла.

Число Кармайкла порядка 2

Согласно Хоу, 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331 является числом Кармайкла второго порядка. Это произведение равно 443 372 888 629 441.

Свойства

Критерий Корсельта может быть обобщён на числа Кармайкла более высокого порядка, как показал Хау. Эвристическое рассуждение, представленное в той же работе, по-видимому, указывает на то, что существует бесконечно много чисел Кармайкла порядка m для любого m. Однако ни одно число Кармайкла порядка 3 и выше пока не известно.