Home Original page

Carmichael Number

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

a^(n-1)-1=0 (mod n)

(1)

for every choice of a satisfying (a,n)=1 (i.e., a and n are relatively prime) with 1<a<n. 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 (a,n)!=1, the congruence of Fermat's little theorem is nonzero, thus identifying a Carmichael number n 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 10^2, 10^3, ... are 0, 1, 7, 16, 43, 105, ... (OEIS A055553; Pinch 1993). The smallest Carmichael numbers having 3, 4, ... factors are 561=3×11×17, 41041=7×11×13×41, 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 k prime factors, there are only a finite number with the least k-2 specified.

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

N=(6k+1)(12k+1)(18k+1)=1296k^3+396k^2+36k+1,

(2)

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

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

C(n)>n^(2/7)

(3)

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

C(n)<nexp(-(lnnlnlnlnn)/(lnlnn))

(4)

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

The Carmichael numbers have the following properties:

1. If a prime p divides the Carmichael number n, then n=1 (mod p-1) implies that n=p (mod p(p-1)).

2. Every Carmichael number is squarefree.

3. An odd composite squarefree number n is a Carmichael number iff n divides the denominator of the Bernoulli number B_(n-1).

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

factorsdigitsdiscoverer
360351Broadhurst (2002)
429094Broadhurst 2003 (Broadhurst 2015b)
51015Caldwell and Dubner
619140Broadhurst 2003 (Broadhurst 2015a)

See also

Carmichael Condition, Lehmer's Totient Problem, Pseudoprime

Explore with Wolfram|Alpha

References

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.Broadhurst, D. "60351-digit 3-Carmichael number." 2 Dec 2002. http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0212&L=nmbrthry&P=R2.Broadhurst, D. "Re: 14241 digits 5-Carmichael number." 29 Aug 2015a. https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1508&L=NMBRTHRY&P=R628.Broadhurst, D. "Re: 25791 digits 4-Carmichael number." 29 Aug 2015b. https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1508&L=NMBRTHRY&P=6285.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 10^(15)." 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 25·10^9." 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."

Referenced on Wolfram|Alpha

Carmichael Number

Cite this as:

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

Subject classifications