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 could expand to $M_{k}(n)=(6n+1)(12n+1)\prod _{i=1}^{k-2}(9\cdot 2^{i}n+1)$ with the restriction, that for $(36\cdot 2^{j}m+1)$ the variable $m\$ is divisible by $2^{j}\$

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 Erdos (1956) and the lower bound is due to Alford, Granville and Pomerance (1994).