for all integers which are relatively prime to . Carmichael numbers are named after American mathematician Robert Carmichael, the term having been introduced by Nicolaas Beeger in 1950 (Øystein Ore had referred to them in 1948 as numbers with the "Fermat property", or "F numbers" for short).
They are infinite in number.
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.
gives a 397-digit Carmichael number that is a strong pseudoprime to all prime bases less than 307:
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.
Korselt was the first who observed the basic properties of Carmichael numbers, but he did not give any examples. In 1910, Carmichael found the first and smallest such number, 561, which explains the name "Carmichael number".
Václav Šimerka listed the first seven Carmichael numbers
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):
These 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, however, remained unnoticed.
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).
Thomas Wright proved that if and are relatively prime,
then there are infinitely many Carmichael numbers in the arithmetic progression ,
Löh and Niebuhr in 1992 found some very large Carmichael numbers, including one with 1,101,518 factors and over 16 million digits.
This has been improved to 10,333,229,505 prime factors and 295,486,761,787 digits, so the largest known Carmichael number is much greater than the largest known prime.
Carmichael numbers have at least three positive prime factors. 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):
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 counts of Carmichael numbers performed by Pinch up to 1021), these conjectures are not yet borne out by the data.
The notion of Carmichael number generalizes to a Carmichael ideal in any number fieldK. 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 integersZ[i] is a Carmichael ideal.
Both prime and Carmichael numbers satisfy the following equality:
Quasi–Carmichael numbers are squarefree composite numbers n with the property that for every prime factor p of n, p + b divides n + b positively with b being any integer besides 0. If b = −1, these are Carmichael numbers, and if b = 1, these are Lucas–Carmichael numbers. The first Quasi–Carmichael numbers are:
The above definition states that a composite integer n is Carmichael
precisely when the nth-power-raising function pn from the ringZn of integers modulo n to itself is the identity function. The identity is the only Zn-algebraendomorphism on Zn so we can restate the definition as asking that pn be an algebra endomorphism of Zn.
As above, pn satisfies the same property whenever n is prime.
The nth-power-raising function pn is also defined on any Zn-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 pn is an endomorphism on every Zn-algebra that can be generated as Zn-module by m elements. Carmichael numbers of order 1 are just the ordinary Carmichael numbers.
An order 2 Carmichael number
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.
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.
^D. H. Lehmer (1976). "Strong Carmichael numbers". J. Austral. Math. Soc. 21 (4): 508–510. doi:10.1017/s1446788700019364. Lehmer proved that no Carmichael number is an Euler-Jacobi pseudoprime to every base relatively prime to it. He used the term strong pseudoprime, but the terminology has changed since then. Strong pseudoprimes are a subset of Euler-Jacobi pseudoprimes. Therefore, no Carmichael number is a strong pseudoprime to every base relatively prime to it.
Pinch, Richard (December 2007). Anne-Maria Ernvall-Hytönen (ed.). The Carmichael numbers up to 1021(PDF). Proceedings of Conference on Algorithmic Number Theory. Vol. 46. Turku, Finland: Turku Centre for Computer Science. pp. 129–131. Retrieved 2017-06-26.
^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.