Carmichael Number

A Carmichael number is an odd composite number which satisfies Fermat's little theorem

(1)

for every choice of satisfying (i.e., and are relatively prime) with . A Carmichael number is therefore a pseudoprime to any base. Carmichael numbers therefore cannot be found to be composite using Fermat's little theorem. However, if , the congruence of Fermat's little theorem is nonzero, thus identifying a Carmichael number as composite.

Carmichael numbers are sometimes called "absolute pseudoprimes" and also satisfy Korselt's criterion. R. D. Carmichael first noted the existence of such numbers in 1910, computed 15 examples, and conjectured that there were infinitely many. In 1956, Erdős sketched a technique for constructing large Carmichael numbers (Hoffman 1998, p. 183), and a proof was given by Alford et al. (1994).

Any solution to Lehmer's totient problem must be a Carmichael number.

The first few Carmichael numbers are 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, ... (OEIS A002997). The number of Carmichael numbers less than , , ... are 0, 1, 7, 16, 43, 105, ... (OEIS A055553; Pinch 1993). The smallest Carmichael numbers having 3, 4, ... factors are , , 825265, 321197185, ... (OEIS A006931).

Carmichael numbers have at least three prime factors. For Carmichael numbers with exactly three prime factors, once one of the primes has been specified, there are only a finite number of Carmichael numbers which can be constructed. Indeed, for Carmichael numbers with prime factors, there are only a finite number with the least specified.

Numbers of the form are Carmichael numbers if each of the factors is prime (Korselt 1899, Ore 1988, Guy 1994). This can be seen since for

(2)

is a multiple of and the least common multiple of , , and is , so modulo each of the primes , , and , hence modulo their product. The first few such Carmichael numbers correspond to , 6, 35, 45, 51, 55, 56, ... (OEIS A046025) and are 1729, 294409, 56052361, 118901521, ... (OEIS A033502).

Let denote the number of Carmichael numbers less than . Then, for all sufficiently large ,

(3)

(Alford et al. 1994), which proves that there are infinitely many Carmichael numbers. The upper bound

(4)

has also been proved (R. G. E. Pinch).

The Carmichael numbers have the following properties:

1. If a prime divides the Carmichael number , then implies that .

2. Every Carmichael number is squarefree.

3. An odd composite squarefree number is a Carmichael number iff divides the denominator of the Bernoulli number .

The largest known Carmichael numbers having a given number of factors are summarized in the following table (updated from Dubner 1989, 1998).

Wolfram Web Resources