In number theory, a Carmichael number is a composite number
Contents
- Overview
- Korselts criterion
- Discovery
- Factorizations
- Distribution
- Generalizations
- Higher order Carmichael numbers
- An order 2 Carmichael number
- Properties
- References
for all integers
Overview
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).
Korselt's criterion
An alternative and equivalent definition of Carmichael numbers is given by Korselt's criterion.
Theorem (A. Korselt 1899): A positive composite integerIt 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
Discovery
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".
That 561 is a Carmichael number can be seen with Korselt's criterion. Indeed,
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.
J. Chernick proved a theorem in 1939 which can be used to construct a subset of Carmichael numbers. The number
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
Löh and Niebuhr in 1992 found some very large Carmichael numbers, including one with 1,101,518 factors and over 16 million digits.
Factorizations
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.
The first Carmichael numbers with
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.
Distribution
Let
In 1953, Knödel proved the upper bound:
for some constant
In 1956, Erdős improved the bound to
for some constant
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
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 conjectured that there were
Carmichael numbers up to X. 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.
Generalizations
The notion of Carmichael number generalizes to a Carmichael ideal in any number field K. For any nonzero prime ideal
When K is larger than the rationals it is easy to write down Carmichael ideals in
Both prime and Carmichael numbers satisfy the following equality:
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 Zn of integers modulo n to itself is the identity function. The identity is the only Zn-algebra endomorphism 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.
Properties
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.