Carmichael number

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

Properties of a Carmichael number

• Every Carmichael number is squarefree and has at least three different prime factors
• For every Carmichael number c is true, that $c-1$ is divisible by $p_{n}-1$ for every of its prime factors $p_{n}$.
• Every Carmichael number is an Euler pseudoprime.
• Every absolute Euler pseudoprime is a Carmichael number.

Chernicks Carmichael numbers

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