TOPICS
Search

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 every base relatively prime to it. For such bases, Fermat's little theorem does not identify a Carmichael number as composite. If (a,n)!=1, then a^(n-1)-1 is nonzero modulo n, thus identifying n as a composite number.

Carmichael numbers are sometimes called "absolute pseudoprimes" and also satisfy Korselt's criterion. Carmichael (1910, pp. 237-238) gave four examples of such numbers. Carmichael (1912, pp. 26-27) listed 15 examples and suggested that there are infinitely many. Hoffman (1998, p. 183) reports that Erdős sketched a technique for constructing large Carmichael numbers in 1956. Alford et al. (1994) proved that there are infinitely many Carmichael numbers.

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 1993a). 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.

For a positive integer k, numbers of the form (6k+1)(12k+1)(18k+1) are Carmichael numbers if each of the factors is prime (Chernick 1939, 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 for a relatively prime to N, 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. For each fixed epsilon>0, Pomerance et al. (1980, p. 1013) proved the upper bound

 C(n)<nexp(-((1-epsilon)lnnlnlnlnn)/(lnlnn))
(4)

for all sufficiently large n depending on epsilon.

Larsen (2023) proved Bertrand's postulate for Carmichael numbers, which guarantees a Carmichael number between x and 2x for every sufficiently large x and gives the stronger short-interval bound stated there.

One way to construct Carmichael numbers is to fix a positive even number L and form products of distinct primes p for which p-1 divides L and p does not divide L. Any composite product n with n=1 (mod L) satisfies Korselt's criterion. Zhang (2011) counted these products when L is the product of the first s primes. For example, he found 8281366855879527 for s=9. Zhang (2015) studied the counts for other choices of L.

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).

Another characterization is obtained by writing the Bernoulli number B_(n-1)=N_(n-1)/D_(n-1) in lowest terms and defining c(n) to be the denominator in lowest terms of N_(n-1)/n+D_(n-1)/n^2. The values of c(n) for n=1, 2, ... begin 1, 1, 1, 16, 1, 36, 1, 64, 27, 100, ... (OEIS A309132). For composite n, the number c(n) is squarefree iff n is a Carmichael number (Adamczewski 2026). An AI-generated proof formally verified in Lean reduces the result, by analysis at each prime, to Korselt's criterion using the von Staudt-Clausen theorem.

Historical reports of large Carmichael numbers with specified numbers of prime factors are summarized in the following table.

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

Randrianantenaina and Uncu (2026) proved that 1729 is the only Carmichael number of the form 2^np^3+1, where p is prime and n>=1 is an integer. It occurs for p=3 and n=6.

Let S_k denote the smallest Carmichael number with exactly k prime factors. Webster and Webster (2026) report computing S_k for every 3<=k<=64 by exhaustive searches. Their algorithm enumerates a partial product P of prime factors and, once Plambda(P)>B, recovers all remaining factors from at most one possible cofactor, where B is the search bound and lambda(P) is the Carmichael function. Under the hypothesis lnS_k=theta(p_k)+O(k), its expected running time is e^(O(k)), where p_k is the kth prime number, theta(x) is the Chebyshev function, and O is big-O notation. The reported exact values come from finite exhaustive searches and do not assume this asymptotic hypothesis. Webster and Webster (2026) attribute the search implementation and much of the asymptotic analysis and its proofs to Claude under their direction, and state that they checked the analysis.

Every Carmichael number n also satisfies GCD(n,phi(n))=1, where phi(n) is the totient function. More generally, this condition characterizes the positive integers n for which every group of order n is cyclic. Webster and Webster (2026, Section 6) report computing the least such integer C_k with exactly k prime factors for k<=64, giving a comparison bound C_k<=S_k for 3<=k<=64. For k=0, 1, 2, ..., the values of C_k begin 1, 2, 15, 255, 5865, ... (OEIS A264907). For 31<=k<=64, they report that the prime factors of C_k cannot be obtained by choosing a first prime and then repeatedly adjoining the least larger prime that preserves GCD(n,phi(n))=1. Thus this greedy construction need not produce C_k.


See also

Bertrand's Postulate for Carmichael Numbers, Carmichael Condition, Lehmer's Totient Problem, Lucas-Carmichael Number, Pseudoprime

Explore with Wolfram|Alpha

References

Adamczewski, T. "OEIS Open: How Many Conjectures Can Language Models Turn into Theorems?" 13 Aug 2026. https://arxiv.org/abs/2608.11941.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. https://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=NMBRTHRY;83fc024f.1508&S=.Carlini, A. and Hosoya, A. "Carmichael Numbers on a Quantum Computer." 5 Aug 1999. https://arxiv.org/abs/quant-ph/9908022.Carmichael, R. D. "Note on a New Number Theory Function." Bull. Amer. Math. Soc. 16, 232-238, 1910.Carmichael, R. D. "On Composite Numbers P Which Satisfy the Fermat Congruence a^(P-1)=1 mod P." Amer. Math. Monthly 19, 22-27, 1912. https://doi.org/10.1080/00029890.1912.11997658.Chernick, J. "On Fermat's Simple Theorem." Bull. Amer. Math. Soc. 45, 269-274, 1939. https://doi.org/10.1090/S0002-9904-1939-06953-X.Dubner, H. "A New Method for Producing Large Carmichael Numbers." Math. Comput. 53, 411-414, 1989.Dubner, H. "Carmichael Number Record." 11 Sep 1998. https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;714f51c5.9809&S=.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.Larsen, D. "Bertrand's Postulate for Carmichael Numbers." Int. Math. Res. Not. 2023, 13072-13098, 2023. https://doi.org/10.1093/imrn/rnac203.Numberphile. "Liar Numbers." Feb. 3, 2014. https://www.youtube.com/watch?v=jbiaz_aHHUQ.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.Randrianantenaina, J. L. and Uncu, A. K. "One More Curious Property of 1729: The Only Carmichael Number of the Form 2^np^3+1 with Prime p." 18 Nov 2026. https://arxiv.org/abs/2611.24275v1.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, Switzerland: 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.Turing. "17-Year-Old Solves a Three Decade Old Conjecture." Aug. 26, 2026. https://www.youtube.com/watch?v=bykiWGYmPgc.Sloane, N. J. A. Sequences A002997/M5462, A006931/M5463, A033502, A046025, A055553, A264907, and A309132 in "The On-Line Encyclopedia of Integer Sequences."Webster, J. and Webster, S. "The Least Carmichael Numbers with k Prime Factors." 16 Nov 2026. https://arxiv.org/abs/2611.21013v1.Zhang, Z. "Counting Carmichael Numbers with Small Seeds." Math. Comput. 80, 437-442, 2011. https://doi.org/10.1090/S0025-5718-2010-02382-8.Zhang, Z. "Estimating the Counts of Carmichael and Williams Numbers with Small Multiple Seeds." Math. Comput. 84, 309-337, 2015. https://doi.org/10.1090/S0025-5718-2014-02837-8.

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