Числа Кармайкла — это особый класс составных чисел, названных в честь американского математика Роберта Кармайкла. Они обладают удивительным свойством: ведут себя как простые числа в малой теореме Ферма, несмотря на то, что являются составными.
Формально, число n называется числом Кармайкла, если выполняются три условия:
Это означает, что числа Кармайкла "обманывают" тест Ферма на простоту – они удовлетворяют условию теоремы, хотя и не являются простыми числами.
Первые пять чисел Кармайкла:
Интересно, что 1729 — это также число Харди-Рамануджана, известное благодаря математическому анекдоту о Г.Х. Харди и С. Рамануджане.
Хотя название связано с Кармайклом, который исследовал эти числа в 1910 году, первые примеры были найдены раньше:
Важный вклад в изучение этих чисел сделал А. Корсельт, сформулировавший критерий:
Составное число n является числом Кармайкла тогда и только тогда, когда оно свободно от квадратов и для каждого простого p, делящего n, число p-1 делит n-1.
В отличие от простых чисел, которые встречаются бесконечно часто, долгое время оставалось открытым вопрос о бесконечности чисел Кармайкла. В 1994 году было доказано, что они действительно образуют бесконечное множество.
Числа Кармайкла важны в криптографии, так как они:
Числа Кармайкла обладают рядом удивительных характеристик:
Исследования чисел Кармайкла продолжаются и сегодня, открывая новые грани их свойств. Они остаются одной из самых интригующих загадок теории чисел, демонстрирующей, насколько сложно может быть поведение "внешне простых" составных чисел.