In number theory, a Carmichael number is a composite positive integer n which satisfies the congruence

\( b^{n-1}\equiv 1\pmod{n} \)

for all integers b which are relatively prime to n (see modular arithmetic). They are named for Robert Carmichael. The Carmichael numbers are the Knödel numbers K1.

Overview

Fermat's little theorem states that all prime numbers have the above property. In this sense, Carmichael numbers are similar to prime numbers; in fact, they are called Fermat pseudoprimes. Carmichael numbers are sometimes also called 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.

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 billion numbers).[1] This makes tests based on Fermat's Little Theorem slightly risky compared to others such as the Solovay-Strassen primality test.
Korselt's criterion

An alternative and equivalent definition of Carmichael numbers is given by Korselt's criterion.

Theorem (A. Korselt 1899): A positive composite integer n is a Carmichael number if and only if n is square-free, and for all prime divisors p of n, it is true that p - 1 | n - 1 (the notation a | b indicates that a divides b).

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 p - 1 | n - 1 results in an even dividing an odd, a contradiction. (The oddness of Carmichael numbers also follows from the fact that -1 is a Fermat witness for any even number.) From the criterion it also follows that Carmichael numbers are cyclic.[2][3]
Discovery

Korselt was the first who observed the basic properties of Carmichael numbers, but he could not find 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, 561 = 3 \cdot 11 \cdot 17 is square-free and 2 | 560, 10 | 560 and 16 | 560.

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

\( 1105 = 5 \cdot 13 \cdot 17 \qquad (4 \mid 1104; 12 \mid 1104; 16 \mid 1104) \)
\( 1729 = 7 \cdot 13 \cdot 19 \qquad (6 \mid 1728; 12 \mid 1728; 18 \mid 1728) \)
\( 2465 = 5 \cdot 17 \cdot 29 \qquad (4 \mid 2464; 16 \mid 2464; 28 \mid 2464) \)
\( 2821 = 7 \cdot 13 \cdot 31 \qquad (6 \mid 2820; 12 \mid 2820; 30 \mid 2820) \)
\( 6601 = 7 \cdot 23 \cdot 41 \qquad (6 \mid 6600; 22 \mid 6600; 40 \mid 6600) \)
\( 8911 = 7 \cdot 19 \cdot 67 \qquad (6 \mid 8910; 18 \mid 8910; 66 \mid 8910). \)

These first seven Carmichael numbers, from 561 to 8911, were all found by the Czech mathematician Václav Šimerka in 1885[5] (thus preceding not just Carmichael but also Korselt, although Šimerka did not find anything like Korselt's criterion). His work, however, remained unnoticed.

J. Chernick[6] proved a theorem in 1939 which can be used to construct a subset of Carmichael numbers. The number (6k + 1)(12k + 1)(18k + 1) 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 n, there are at least \( n^{2/7} \) Carmichael numbers between 1 and n.[7]

Löh and Niebuhr in 1992 found some huge Carmichael numbers, including one with 1,101,518 factors and over 16 million digits.
Properties
Factorizations

Carmichael numbers have at least three positive prime factors. The first Carmichael numbers with k = 3, 4, 5, \ldots prime factors are (sequence A006931 in OEIS):

k
3	\( 561 = 3 \cdot 11 \cdot 17\, \)
4	\( 41041 = 7 \cdot 11 \cdot 13 \cdot 41\, \)
5	\( 825265 = 5 \cdot 7 \cdot 17 \cdot 19 \cdot 73\, \)
6	\( 321197185 = 5 \cdot 19 \cdot 23 \cdot 29 \cdot 37 \cdot 137\, \)
7	\( 5394826801 = 7 \cdot 13 \cdot 17 \cdot 23 \cdot 31 \cdot 67 \cdot 73\, \)
8	\( 232250619601 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 31 \cdot 37 \cdot 73 \cdot 163\, \)
9	\( 9746347772161 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 31 \cdot 37 \cdot 41 \cdot 641\, \)

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

i
1	\( 41041 = 7 \cdot 11 \cdot 13 \cdot 41\, \)
2	\( 62745 = 3 \cdot 5 \cdot 47 \cdot 89\, \)
3	\( 63973 = 7 \cdot 13 \cdot 19 \cdot 37\, \)
4	\( 75361 = 11 \cdot 13 \cdot 17 \cdot 31\, \)
5	\( 101101 = 7 \cdot 11 \cdot 13 \cdot 101\, \)
6	\( 126217 = 7 \cdot 13 \cdot 19 \cdot 73\, \)
7	\( 172081 = 7 \cdot 13 \cdot 31 \cdot 61\, \)
8	\( 188461 = 7 \cdot 13 \cdot 19 \cdot 109\, \)
9	\( 278545 = 5 \cdot 17 \cdot 29 \cdot 113\, \)
10	\( 340561 = 13 \cdot 17 \cdot 23 \cdot 67\, \)

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 in two different ways.
Distribution

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

n	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
k	1	7	16	43	105	255	646	1547	3605	8241	19279	44706	105212	246683	585355	1401644	3381806	8220777	20138200

In 1956, Erdős proved that[8]

\( C(X) < X \exp\left(\frac{-k \log X \log \log \log X}{\log \log X}\right) \)

for some constant k. He further gave a heuristic argument suggesting that this upper bound should be close to the true growth rate of C(X). The table below gives approximate minimal values for the constant k in the Erdős bound for \( X=10^n \)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 the other direction, Alford, Granville and Pomerance proved in 1994[7] that for sufficiently large X,

\( C(X) > X^{2/7}. \)

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

\( C(X) > X^{0.332} \)

and then has subsequently improved the exponent to just over 1/3.

Regarding the asymptotic distribution of Carmichael numbers, there have been several conjectures. In 1956, Erdős[8] conjectured that there were \( X^{1-o(1)} \) Carmichael numbers for X sufficiently large. In 1981, Pomerance[10] sharpened Erdős' heuristic arguments to conjecture that there are

\( X^{1-{\frac{\{1+o(1)\}\log\log\log X}{\log\log X}}} \)

Carmichael numbers up to X. However, inside current computational ranges (such as the counts of Carmichael numbers performed by Pinch[1] up to 1021), these conjectures are not yet borne out by the data. Utilizing finer estimates for the distribution of smooth numbers, Aran Nayebi[11] has proposed a conjecture (defined as the function a(x) on pg. 31) that is asymptotically the same as Pomerance's, but more closely models the actual distribution of Carmichael numbers for the small bounds computed by Pinch and may provide accurate predictions for counts with bounds (< 10100) yet to be computed, particularly since its derivation involves a sharpening of Pomerance's (and Erdős') heuristic arguments.
Generalizations

The notion of Carmichael number generalizes to a Carmichael ideal in any number field K. For any nonzero prime ideal \( \mathfrak p \) in \( {\mathcal O}_K, \) we have \( \alpha^{{\rm N}(\mathfrak p)} \equiv \alpha \bmod {\mathfrak p} \) for all \( \alpha \) in \( {\mathcal O}_K, \) where \( {\rm N}(\mathfrak p) \) is the norm of the ideal \( \mathfrak p \). (This generalizes Fermat's little theorem, that \( m^p \equiv m \bmod p \) for all integers m when p is prime.) Call a nonzero ideal \( {\mathfrak a} \) in \( {\mathcal O}_K \) Carmichael if it is not a prime ideal and \( \alpha^{{\rm N}(\mathfrak a)} \equiv \alpha \bmod {\mathfrak a} \) for all \( \alpha \in {\mathcal O}_K \), where \( {\rm N}({\mathfrak a}) \) is the norm of the ideal \( {\mathfrak a}. \) When K is \( \mathbf Q \) , the ideal \({\mathfrak a} \) is principal, and if we let a be its positive generator then the ideal \( {\mathfrak a} = (a) \) 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 \( {\mathcal O}_K: \) for any prime number p that splits completely in K, the principal ideal \( p{\mathcal O}_K \) is a Carmichael ideal. Since infinitely many prime numbers split completely in any number field, there are infinitely many Carmichael ideals in \( {\mathcal O}_K. \) 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:

\( \gcd (\sum_{x=1}^{n-1} x^{n-1}, n)\equiv 1 \)

Higher-order Carmichael numbers

Carmichael numbers can be generalized using concepts of abstract algebra.

The above definition states that a composite integer n is Carmichael precisely when the nth-power-raising function pn from the ring Z_n of integers modulo n to itself is the identity function. The identity is the only Z_n-algebra endomorphism on Z_n so we can restate the definition as asking that pn be an algebra endomorphism of Z_n. As above, pn satisfies the same property whenever n is prime.

The nth-power-raising function pn is also defined on any Z_n-algebra A. A theorem states that n is prime if and only if all such functions pn are algebra endomorphisms.

In-between these two conditions lies the definition of Carmichael number of order m for any positive integer m as any composite number n such that p_n is an endomorphism on every Z_n-algebra that can be generated as Z_n-module by m elements. Carmichael numbers of order 1 are just the ordinary Carmichael numbers.
Properties

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

A heuristic argument, given in the same paper, appears to suggest that there are infinitely many Carmichael numbers of order m, for any m. However, not a single Carmichael number of order 3 or above is known.
Notes

^ a b c Richard Pinch, "The Carmichael numbers up to 1021", May 2007.
^ Carmichael Multiples of Odd Cyclic Numbers "Any divisor of a Carmichael number must be an odd cyclic number"
^ Proof sketch: If n is square-free but not cyclic, p_i | p_j - 1 for two prime factors p_i and p_j of n. But if n satisfies Korselt then p_j - 1 | n - 1, so by transitivity of the "divides" relation p_i | n - 1. But p_i is also a factor of n, a contradiction.
^ R. D. Carmichael (1910). "Note on a new number theory function". Bulletin of the American Mathematical Society 16 (5): 232–238.
^ 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.
^ Chernick, J. (1939). "On Fermat's simple theorem". Bull. Amer. Math. Soc. 45: 269–274. doi:10.1090/S0002-9904-1939-06953-X.
^ a b W. R. Alford, A. Granville, C. Pomerance (1994). "There are Infinitely Many Carmichael Numbers". Annals of Mathematics 139: 703–722. doi:10.2307/2118576.
^ a b Erdős, P. (1956). "On pseudoprimes and Carmichael numbers". Publ. Math. Debrecen 4: 201–206. MR79031.
^ Glyn Harman (2005). "On the number of Carmichael numbers up to x". Bull. Lond. Math. Soc. 37: 641–650. doi:10.1112/S0024609305004686.
^ Pomerance, C. (1981). "On the distribution of pseudoprimes". Math. Comp. 37: 587–593. JSTOR 2007448.
^ Nayebi, Aran (2011). "On the distribution of Carmichael numbers". Rejecta Math. 2: 24–43.
^ Everett W. Howe. "Higher-order Carmichael numbers." Mathematics of Computation 69 (2000), pp. 1711–1719.

References

Carmichael, R. D. (1910). "Note on a new number theory function". Bulletin of the American Mathematical Society 16 (5): 232–238.
Carmichael, R. D. (1912). "On composite numbers P which satisfy the Fermat congruence a^{P-1}\equiv 1\bmod P". American Mathematical Monthly 19 (2): 22–27. doi:10.2307/2972687.
Chernick, J. (1939). "On Fermat's simple theorem". Bull. Amer. Math. Soc. 45: 269–274. doi:10.1090/S0002-9904-1939-06953-X.
Korselt, A. R. (1899). "Problème chinois". L'intermédiaire des mathématiciens 6: 142–143.
Löh, G.; Niebuhr, W. (1996). "A new algorithm for constructing large Carmichael numbers". Math. Comp. 65: 823–836. doi:10.1090/S0025-5718-96-00692-8.
Ribenboim, P. (1989). The Book of Prime Number Records. Springer. ISBN 978-0-387-97042-4.
Šimerka, V. (1885). "Zbytky z arithmetické posloupnosti (On the remainders of an arithmetic progression)". Časopis pro pěstování matematiky a fysiky 14 (5): 221–225.

External links