Carmichael number

A Carmichael number is a composite number, who is named after the mathematician Robert Daniel Carmichael. A Carmichael number c satisfies for every integer a, that $a^{c}-a$ is divisible by c. A Carmichael number c satisfies also the conrgruence $a^{c-1}\equiv 1{\pmod {c}}$, if $\operatorname {gcd} (a,c)=1$. In 1994 Pomerance, Alford and Granville proved that there exist infinitely many Carmichael numbers.

Properties of a Carmichael number

Every Carmichael number is an Euler pseudoprime. Every abolute Euler pseudoprime is a Carmichael number. A Carmichael number is squarefree and every Carmichael number has three different prime factors or more. Every Carmichael number c satisfies for every of his prime factors $p_{n}$ that $c-1$ is divisible by $p_{n}-1$.

Chernicks Carmichael numbers

J. Chernick found in 1939 a way to construct Carmichael numbers. If, for a natural number n, the three numbers 6n+1, 12n+1 and 18n+1 are prime numbers, the product $(6n+1)\cdot (12n+1)\cdot (18n+1)$ is a Carmichael number. Equivalent to this is that if m, 2m-1 and 3m-2 are prime numbers, then the product $m\cdot (2m-1)\cdot (3m-1)$ is a Carmichael number.

Further reading

• Richard E. Crandall and Carl Pomerance: Prime Numbers. A Computational Perspective. Springer Verlag, ISBN 0-387-25282-7
• Paolo Ribenboim: The New Book of Prime Number Records. Springer Verlag, 1996, ISBN 0-387-94457-5