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 sometimes 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, ... (Sloane's A002997). The number of Carmichael numbers less than , , ... are 0, 1, 7, 16, 43, 105, ... (Sloane's A055553; Pinch 1993). The smallest Carmichael numbers having 3, 4, ... factors are , , 825265, 321197185, ... (Sloane's 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, ... (Sloane's A046025) and are 1729, 294409, 56052361, 118901521, ... (Sloane's 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 (Dubner 1989, 1998).

Alford, W. R.; Granville, A.; and Pomerance, C. "There are Infinitely Many Carmichael Numbers." Ann. Math. 139, 703-722, 1994.

Beyer, W. H. CRC Standard Mathematical Tables, 28th ed. Boca Raton, FL: CRC Press, p. 87, 1987.

Carlini, A. and Hosoya, A. "Carmichael Numbers on a Quantum Computer." 5 Aug 1999. http://arxiv.org/abs/quant-ph/9908022/.

Carmichael, R. D. "Note on a New Number Theory Function." Bull. Amer. Math. Soc. 16, 232-238, 1910.

Dubner, H. "A New Method for Producing Large Carmichael Numbers." Math. Comput. 53, 411-414, 1989.

Dubner, H. "Carmichael Number Record." 11 Sep 1998. http://listserv.nodak.edu/scripts/wa.exe?A2=ind9809&L=NMBRTHRY&P=795.

Guy, R. K. "Carmichael Numbers." §A13 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 30-32, 1994.

Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, pp. 182-183, 1998.

Korselt, A. "Problème chinois." L'intermédiaire math. 6, 143-143, 1899.

Ore, Ø. Number Theory and Its History. New York: Dover, 1988.

Pinch, R. G. E. "The Carmichael Numbers up to ." Math. Comput. 61, 381-391, 1993a.

Pinch, R. G. E. "Some Primality Testing Algorithms." Not. Amer. Math. Soc. 40, 1203-1210, 1993b.

Pinch, R. G. E. ftp://ftp.dpmms.cam.ac.uk/pub/Carmichael/table.

Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. Jr. "The Pseudoprimes to ." Math. Comput. 35, 1003-1026, 1980.

Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, pp. 118-125, 1996.

Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Basel: Birkhäuser, pp. 89-90 and 94-95, 1994.

Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 116, 1993.

Sloane, N. J. A. Sequences A002997/M5462, A006931/M5463, A033502, A046025, and A055553 in "The On-Line Encyclopedia of Integer Sequences."

CITE THIS AS:

Weisstein, Eric W. "Carmichael Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/CarmichaelNumber.html