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

---

В теории чисел число Кармайкла — составное число , которое в модульной арифметике удовлетворяет соотношению конгруэнтности :${\displaystyle п}$

для всех целых чисел . ^[1] Отношение также может быть выражено ^{[2] [ неудачная проверка ]} в форме:${\displaystyle б}$

для всех целых чисел , которые относительно просты . Числа Кармайкла названы в честь американского математика Роберта Кармайкла . Этот термин был введен Николаасом Бигером в 1950 году ( Эйстейн Оре называл их в 1948 году числами со «свойством Ферма», или для краткости «числами F » ^[3] ). Их число бесконечно . ^[4]${\displaystyle б}$${\displaystyle п}$

Они представляют собой сравнительно редкие случаи, когда строгое обращение Малой теоремы Ферма не выполняется. Этот факт исключает использование этой теоремы в качестве абсолютного критерия простоты . ^[5]

Маленькая теорема Ферма утверждает, что если — простое число , то для любого целого числа это число кратно . Числа Кармайкла — это составные числа, обладающие одним и тем же свойством. Числа Кармайкла также называют псевдопростыми числами Ферма или абсолютными псевдопростыми числами Ферма . Число Кармайкла пройдет тест на простоту Ферма по каждому основанию, относительно простому этому числу, даже если оно на самом деле не является простым. Это делает тесты, основанные на Малой теореме Ферма, менее эффективными, чем сильные тесты на вероятность простых чисел, такие как тест простоты Бэйли-ПСВ и тест простоты Миллера-Рабина .${\displaystyle p}$ ${\displaystyle b}$${\displaystyle b^{p}-b}$${\displaystyle p}$${\displaystyle b}$

Однако ни одно число Кармайкла не является псевдопростым или сильным псевдопростым по отношению к каждому основанию, относительно простому ему ^[6], поэтому теоретически либо критерий Эйлера, либо сильный вероятностный простой критерий могут доказать, что число Кармайкла на самом деле является , композит.

---