In number theory, a Carmichael number is a composite number which in modular arithmetic satisfies the congruence relation:
for all integers . The relation may also be expressed in the form:
for all integers that are relatively prime to . They are infinite in number.
They constitute the comparatively rare instances where the strict converse of Fermat's Little Theorem does not hold. This fact precludes the use of that theorem as an absolute test of primality.
The Carmichael numbers form the subset K<sub>1</sub> of the Knödel numbers.
The Carmichael numbers were named after the American mathematician Robert Carmichael by Nicolaas Beeger, in 1950. ÃÂystein Ore had referred to them in 1948 as numbers with the "Fermat property", or "F numbers" for short.
Fermat's little theorem states that if is a prime number, then for any integer , the number is an integer multiple of . Carmichael numbers are composite numbers which have the same property. Carmichael numbers are also called Fermat pseudoprimes or absolute Fermat pseudoprimes. A Carmichael number will pass a Fermat primality test to every base relatively prime to the number, even though it is not actually prime. This makes tests based on Fermat's Little Theorem less effective than strong probable prime tests such as the BaillieâÂÂPSW primality test and the MillerâÂÂRabin primality test.
However, no Carmichael number is either an EulerâÂÂJacobi pseudoprime or a strong pseudoprime to every base relatively prime to it so, in theory, either an Euler or a strong probable prime test could prove that a Carmichael number is, in fact, composite.
Arnault gives a 397-digit Carmichael number that is a strong pseudoprime to all prime bases less than 307:
where
is a 131-digit prime. is the smallest prime factor of , so this Carmichael number is also a (not necessarily strong) pseudoprime to all bases less than .
As numbers become larger, Carmichael numbers become increasingly rare. For example, there are Carmichael numbers between 1 and 10<sup>21</sup> (approximately one in 50 trillion () numbers).
An alternative and equivalent definition of Carmichael numbers is given by Korselt's criterion.
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. Additionally, it follows that there are no Carmichael numbers with exactly two prime divisors.
The first seven Carmichael numbers, from 561 to 8911, were all found by the Czech mathematician Václav à  imerka in 1885 (thus preceding not just Carmichael but also Korselt, although à  imerka did not find anything like Korselt's criterion). His work, published in Czech scientific journal ÃÂasopis pro pÃÂstovánàmatematiky a fysiky, however, remained unnoticed.
Korselt was the first who observed the basic properties of Carmichael numbers, but he did not give any examples.
That 561 is a Carmichael number can be seen with Korselt's criterion. The first seven Carmichael numbers are :
In 1910, Carmichael himself also published the smallest such number, 561, and the numbers were later named after him.
Jack Chernick 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 W. R. (Red) Alford, Andrew Granville and Carl Pomerance used a bound on Olson's constant to show 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 .
Thomas Wright proved that if and are relatively prime, then there are infinitely many Carmichael numbers in the arithmetic progression , where .
Löh and Niebuhr in 1992 found some very large Carmichael numbers, including one with factors and over 16 million digits. This has been improved to prime factors and digits, so the largest known Carmichael number is much greater than the largest known prime.
Carmichael numbers have at least three prime factors. The first Carmichael numbers with prime factors are :
The first Carmichael numbers with 4 prime factors are :
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 :
In 1953, Knödel proved the upper bound:
for some constant .
In 1956, Erdà Âs improved the bound to
for some constant . He further gave a heuristic argument suggesting that this upper bound should be close to the true growth rate of .
In the other direction, Alford, Granville and Pomerance proved in 1994 that for sufficiently large X,
In 2005, this bound was further improved by Harman to
who subsequently improved the exponent to .
Regarding the asymptotic distribution of Carmichael numbers, there have been several conjectures. In 1956, Erdà Âs conjectured that there were Carmichael numbers for X sufficiently large. In 1981, Pomerance sharpened Erdà Âs' heuristic arguments to conjecture that there are at least
Carmichael numbers up to , where .
However, inside current computational ranges (such as the count of Carmichael numbers performed by Goutier up to 10<sup>22</sup>), these conjectures are not yet borne out by the data; empirically, the exponent is for the highest available count (C(X) = 49679870 for X = 10<sup>22</sup>).
In 2021, Daniel Larsen proved an analogue of Bertrand's postulate for Carmichael numbers first conjectured by Alford, Granville, and Pomerance in 1994. Using techniques developed by Yitang Zhang and James Maynard to establish results concerning small gaps between primes, his work yielded the much stronger statement that, for any and sufficiently large in terms of , there will always be at least
Carmichael numbers between and
The notion of Carmichael number generalizes to a Carmichael ideal in any number field . 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 when 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 is , the ideal is principal, and if we let be its positive generator then the ideal is Carmichael exactly when is a Carmichael number in the usual sense.
When is larger than the rationals it is easy to write down Carmichael ideals in : for any prime number that splits completely in , 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 is any prime number that is 1 mod 4, the ideal in the Gaussian integers is a Carmichael ideal.
Both prime and Carmichael numbers satisfy the following equality:
A positive composite integer is a LucasâÂÂCarmichael number if and only if is square-free, and for all prime divisors of , it is true that . The first LucasâÂÂCarmichael numbers are:
QuasiâÂÂCarmichael numbers are squarefree composite numbers with the property that for every prime factor of , divides positively with being any integer besides 0. If , these are Carmichael numbers, and if , these are LucasâÂÂCarmichael numbers. The first QuasiâÂÂCarmichael numbers are:
An n-Knödel number for a given positive integer n is a composite number m with the property that each coprime to m satisfies . The case are 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 p<sub>n</sub> from the ring Z<sub>n</sub> of integers modulo n to itself is the identity function. The identity is the only Z<sub>n</sub>-algebra endomorphism on Z<sub>n</sub> so we can restate the definition as asking that p<sub>n</sub> be an algebra endomorphism of Z<sub>n</sub>. As above, p<sub>n</sub> satisfies the same property whenever n is prime.
The nth-power-raising function p<sub>n</sub> is also defined on any Z<sub>n</sub>-algebra A. A theorem states that n is prime if and only if all such functions p<sub>n</sub> 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<sub>n</sub> is an endomorphism on every Z<sub>n</sub>-algebra that can be generated as Z<sub>n</sub>-module by m elements. Carmichael numbers of order 1 are just the ordinary Carmichael numbers.
According to Howe, 17 ÷ 31 ÷ 41 ÷ 43 ÷ 89 ÷ 97 ÷ 167 ÷ 331 is an order 2 Carmichael number. This product is equal to .
Korselt's criterion can be generalized to higher-order Carmichael numbers, as shown by Howe.
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.