Carmichael number

A Carmichael number is a composite number 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 also satisfies the congruence $\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 square-free and has at least three different prime factors
• For every Carmichael number c it holds that $c-1$ is divisible by $p_{n}-1$ for every one of its prime factors $p_{n}$.
• Every Carmichael number is an Euler pseudoprime.
• Every absolute Euler pseudoprime is a Carmichael number.

Chernick's 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 M_{3}(n)=(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.

To construct Carmichael numbers with $\scriptstyle M_{3}(n)=(6n+1)\cdot (12n+1)\cdot (18n+1)$, you could only use numbers $n\$ which ends with 0, 1, 5 or 6.

This way to construct Carmichael numbers could expand to $M_{k}(n)=(6n+1)(12n+1)\prod _{i=1}^{k-2}(9\cdot 2^{i}n+1)$ with the restiction, that for $(36\cdot 2^{j}m+1)$ the variable $m\$ is divisible bei $2^{j}\$

Further reading

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

Links

• List of Carmichael numbers between 561 and 2,301,745,249