Может ли составное нечетное число n быть псевдопростым по всем взаимно-простым с ним основаниям b? Забегая вперед, скачем, что «да».
Заметим, что если b взаимно просто с n, то сравнение bn ≡ b (mod n)
равносильно
bn-1 ≡ 1 (mod n).
А существует ли такое нечетное натуральное n, которое, будучи составным, удовлетворяет сравнениям bn ≡ b (mod n) для всех целых b?
Первым привел пример таких чисел n математик Р. Д. Кармайкл в своей работе, опубликованной в 1912 году. Поэтому они и называются числами Кармайкла.
Нечетное натуральное n называется числом Кармайкла, если оно составное и
bn ≡ b (mod n) для всех целых b.
Конечно, достаточно проверить это сравнение только для чисел, удовлетворяющих неравенству 1 < b < n-1, поскольку мы работаем по модулю n.
Как показал сам Кармайкл, наименьшее из чисел, открытых им, равно 561. Докажем, что число 561 – число Кармайкла:
561 = 3*11*17
b561 ≡ b (mod 561)
b561 ≡ b (mod 17)
далее необходимо рассмотреть два случая:
1)число 17 делит b. В этой ситуации обе части уравнения b561 ≡ b (mod 17)
сравнимы с 0 по модулю 17, т.е. сравнение справедливо.
2)Число 17 не делит b.
b16 ≡ 1 (mod 17)
561 = 35*16+1, поэтому
b561 ≡ (b16)35 * b ≡ b (mod 17)