Carmichael number

A Carmichael number is a composite number named after the mathematician Robert Daniel Carmichael. A Carmichael number $\scriptstyle c\$ divides $\scriptstyle a^{c}-a\$ for every integer $\scriptstyle a\$. 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

• 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 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 mey be extended to

$M_{k}(n)=(6n+1)(12n+1)\prod _{i=1}^{k-2}(9\cdot 2^{i}n+1)\,$

with the condition that each of the factors is prime and that $n\$ is divisible by $2^{k-4}$.

Distribution of Carmichael numbers

Let C(X) denote the number of Carmichael numbers less than or equal to X. Then for all sufficiently large X

$X^{2/7}<C(X)<X\exp(-\log X\log \log \log X/\log \log X).\,$

The upper bound is due to Erdős(1956) and Pomerance, Selfridge and Wagstaff (1980) and the lower bound is due to Alford, Granville and Pomerance (1994). The asymptotic rate of growth of C(X) is not known.