Carmichael number

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In number theory, a Carmichael number is a composite number which satisfies the modular arithmetic congruence relation:

for all integers which are relatively prime to . They are named for Robert Carmichael. The Carmichael numbers are the subset K1 of the Knödel numbers.


Fermat's little theorem states that if p is a prime number, then for any integer b, the number b p − b is an integer multiple of p. Carmichael numbers are composite numbers which have the same property of modular arithmetic congruence. In fact, Carmichael numbers are also called Fermat pseudoprimes or absolute Fermat pseudoprimes. Carmichael numbers are important because they pass the Fermat primality test but are not actually prime. Since Carmichael numbers exist, this primality test cannot be relied upon to prove the primality of a number, although it can still be used to prove a number is composite. This makes tests based on Fermat's Little Theorem risky compared to other more stringent tests such as the Solovay-Strassen primality test or a strong pseudoprime test. Still, as numbers become larger, Carmichael numbers become very rare. For example, there are 20,138,200 Carmichael numbers between 1 and 1021 (approximately one in 50 trillion (5*1013) numbers).[1]

Korselt's criterion[edit]


Theorem (A. Korselt 1899): A positive composite integer is a Carmichael number if and only if is square-free, and for all prime divisors of , it is true that .

It follows from this theorem that all Carmichael numbers are odd, since any even composite number that is square-free (and hence has only one prime factor of two) will have at least one odd prime factor, and thus results in an even dividing an odd, a contradiction. (The oddness of Carmichael numbers also follows from the fact that is a Fermat witness for any even composite number.) From the criterion it also follows that Carmichael numbers are cyclic.[2][3] Additionally, it follows that there are no Carmichael numbers with exactly two prime factors.


Korselt was the first who observed the basic properties of Carmichael numbers, but he did not give any examples. In 1910, Carmichael[4] found the first and smallest such number, 561, which explains the name "Carmichael number".

That 561 is a Carmichael number can be seen with Korselt's criterion. Indeed, is square-free and , and .

The next six Carmichael numbers are (sequence A002997 in the OEIS):


J. Chernick[6] proved a theorem in 1939 which can be used to construct a subset of Carmichael numbers. The number is a Carmichael number if its three factors are all prime. Whether this formula produces an infinite quantity of Carmichael numbers is an open question (though it is implied by Dickson's conjecture).

Paul Erdős heuristically argued there should be infinitely many Carmichael numbers. In 1994 it was shown by W. R. (Red) Alford, Andrew Granville and Carl Pomerance that there really do exist infinitely many Carmichael numbers. Specifically, they showed that for sufficiently large , there are at least Carmichael numbers between 1 and .[7]




Carmichael numbers have at least three positive prime factors. For some fixed R, there are infinitely many Carmichael numbers with exactly R factors; in fact, there are infinitely many such R.[8]

The first Carmichael numbers with prime factors are (sequence A006931 in the OEIS):


The first Carmichael numbers with 4 prime factors are (sequence A074379 in the OEIS):


The second Carmichael number (1105) can be expressed as the sum of two squares in more ways than any smaller number. The third Carmichael number (1729) is the Hardy-Ramanujan Number: the smallest number that can be expressed as the sum of two cubes (of positive numbers) in two different ways.


Let denote the number of Carmichael numbers less than or equal to . The distribution of Carmichael numbers by powers of 10 (sequence A055553 in the OEIS):[1]

0 0 1 7 16 43 105 255 646 1547 3605 8241 19279 44706 105212 246683

In 1953, Knödel proved the upper bound:

for some constant .

In 1956, Erdős improved the bound to[9]

for some constant . He further gave a heuristic argument suggesting that this upper bound should be close to the true growth rate of . The table below gives approximate minimal values for the constant k in the Erdős bound for as n grows:

4 6 8 10 12 14 16 18 20 21
k 2.19547 1.97946 1.90495 1.86870 1.86377 1.86293 1.86406 1.86522 1.86598 1.86619


In 2005, this bound was further improved by Harman[10] to

and then has subsequently improved the exponent to just over .

Regarding the asymptotic distribution of Carmichael numbers, there have been several conjectures. In 1956, Erdős[9] conjectured that there were Carmichael numbers for X sufficiently large. In 1981, Pomerance[11] sharpened Erdős' heuristic arguments to conjecture that there are



The notion of Carmichael number generalizes to a Carmichael ideal in any number field K. For any nonzero prime ideal in , we have for all in , where is the norm of the ideal . (This generalizes Fermat's little theorem, that for all integers m when p is prime.) Call a nonzero ideal in Carmichael if it is not a prime ideal and for all , where is the norm of the ideal . When K is , the ideal is principal, and if we let a be its positive generator then the ideal is Carmichael exactly when a is a Carmichael number in the usual sense.

When K is larger than the rationals it is easy to write down Carmichael ideals in : for any prime number p that splits completely in K, the principal ideal is a Carmichael ideal. Since infinitely many prime numbers split completely in any number field, there are infinitely many Carmichael ideals in . For example, if p is any prime number that is 1 mod 4, the ideal (p) in the Gaussian integers Z[i] is a Carmichael ideal.

Both prime and Carmichael numbers satisfy the following equality:

Higher-order Carmichael numbers[edit]

Carmichael numbers can be generalized using concepts of abstract algebra.




An order 2 Carmichael number[edit]

According to Howe, 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331 is an order 2 Carmichael number. This product is equal to 443,372,888,629,441.


Korselt's criterion can be generalized to higher-order Carmichael numbers, as shown by Howe.[12]



  3. ^ Proof sketch: If is square-free but not cyclic, for two prime factors and of . But if satisfies Korselt then , so by transitivity of the "divides" relation . But is also a factor of , a contradiction.
  4. ^ R. D. Carmichael (1910). "Note on a new number theory function". Bulletin of the American Mathematical Society. 16 (5): 232–238. doi:10.1090/s0002-9904-1910-01892-9. 
  5. ^ V. Šimerka (1885). "Zbytky z arithmetické posloupnosti (On the remainders of an arithmetic progression)". Časopis pro pěstování matematiky a fysiky. 14 (5): 221–225. 
  6. ^ Chernick, J. (1939). "On Fermat's simple theorem" (PDF). Bull. Amer. Math. Soc. 45: 269–274. doi:10.1090/S0002-9904-1939-06953-X. 
  7. ^ a b W. R. Alford; Andrew Granville; Carl Pomerance (1994). "There are Infinitely Many Carmichael Numbers" (PDF). Annals of Mathematics. 139: 703–722. doi:10.2307/2118576. 
  8. ^ Wright, Thomas (2016-06-01). "Factors of Carmichael numbers and a weak k-tuples conjecture". Journal of the Australian Mathematical Society. Australian Mathematical Publishing Association Inc. 100 (3): 421–429. doi:10.1017/S1446788715000427. Retrieved 2016-08-13. 
  9. ^ a b Erdős, P. (1956). "On pseudoprimes and Carmichael numbers" (PDF). Publ. Math. Debrecen. 4: 201–206. MR 79031. 
  10. ^ Glyn Harman (2005). "On the number of Carmichael numbers up to x". Bulletin of the London Mathematical Society. 37: 641–650. doi:10.1112/S0024609305004686. 
  11. ^ Pomerance, C. (1981). "On the distribution of pseudoprimes". Math. Comp. 37: 587–593. doi:10.1090/s0025-5718-1981-0628717-0. JSTOR 2007448. 


External links[edit]