Carmichael Number

A Carmichael number is an integer $ n $ which is composed (therefore not a prime number) such that for any integer $ a $, the following formula is true $$ a^{{n-1}} \equiv 1 \mod{n} \iff a^{{n}} \equiv a \mod{n} $$

So, for any integer $ p $ coprime with $ n $, the property $ n \mid p^n-p $ is verified (which reads $ n $ divides $ p^n-p $ so $ p^n-p $ is a multiple of $ n $)

Example: $ 8911 $ is a Carmichael number $ 8911 = 7 \times 19 \times 67 $

Sometimes the expression is rewritten $ n \mid p^{n–1}–1 $ which allows to realize that a Carmichael number satisfies Fermat's little theorem: $$ p^{n-1}- \equiv 0 \mod {n} $$

Carmichael numbers are also called strong pseudo-prime numbers or Euler-Jacobi pseudo-prime numbers.

There is no formula to quickly find all Carmichael numbers but it is possible to use an algorithm which is conditioned by a primality test and the verification of $ a^{{n-1}} \equiv 1 \mod{n} $

There are infinitely many Carmichael numbers (proof from Alford et al. 1994)

The smallest Carmichael number is $ 561 $ which has for prime factors decomposition $ 561 = 3 \times 11 \times 17 $

Here is the list of Carmichael's numbers up to 1 million: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 9976

OEIS Sequence A002997 here (link)

Robert Daniel Carmichael was an American mathematician who published a study on these numbers in 1912.