CARMICHAEL NUMBER

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 ''K''₁.

Contents

Overview

Properties

Distribution

Higher-order Carmichael numbers

Properties

References

External links

Overview

Fermat's little theorem states that all prime numbers have that property. In this sense, Carmichael numbers are similar to prime numbers. They are called Fermat pseudoprimes. Carmichael numbers are sometimes also called 'absolute Fermat pseudoprimes'.
Carmichael numbers are important because they can fool the Fermat primality test, thus they are always ''fermat liars''. 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 1,401,644 Carmichael numbers between 1 and 10¹⁸ (approximately one in 700 billion numbers.)^[1] This makes tests based on Fermat's Little Theorem slightly risky compared to others such as the Solovay-Strassen primality test.
An alternative and equivalent definition of Carmichael numbers is given by Korselt's theorem.
'Theorem' (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.
Korselt was the first who observed these properties, but he could not find an example. In 1910 Carmichael found the first and smallest such number, 561, and hence the name.
That 561 is a Carmichael number can be seen with Korselt's theorem. Indeed, $561\; =\; 3\; cdot\; 11\; cdot\; 17$ is squarefree and $2\; |\; 560$, $10\; |\; 560$ and $16\; |\; 560$.
The next few Carmichael numbers are :
:$1105\; =\; 5\; cdot\; 13\; cdot\; 17\; qquad\; (4\; |\; 1104,\; 12\; |\; 1104,\; 16\; |\; 1104)$
:$1729\; =\; 7\; cdot\; 13\; cdot\; 19\; qquad\; (6\; |\; 1728,\; 12\; |\; 1728,\; 18\; |\; 1728)$
:$2465\; =\; 5\; cdot\; 17\; cdot\; 29\; qquad\; (4\; |\; 2464,\; 16\; |\; 2464,\; 28\; |\; 2464)$
:$2821\; =\; 7\; cdot\; 13\; cdot\; 31\; qquad\; (6\; |\; 2820,\; 12\; |\; 2820,\; 30\; |\; 2820)$
:$6601\; =\; 7\; cdot\; 23\; cdot\; 41\; qquad\; (6\; |\; 6600,\; 22\; |\; 6600,\; 40\; |\; 6600)$
:$8911\; =\; 7\; cdot\; 19\; cdot\; 67\; qquad\; (6\; |\; 8910,\; 18\; |\; 8910,\; 66\; |\; 8910)$
J. Chernick 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.
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 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$.^[2]
Löh and Niebuhr in 1992 found some of these huge Carmichael numbers including one with 1,101,518 factors and over 16 million digits.

Properties

Carmichael numbers have at least three positive prime factors. The first Carmichael numbers with $k\; =\; 3,\; 4,\; 5,\; ldots$ prime factors are :

''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 :

''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$

Incidentally, the first Carmichael number (561) is expressible as the sum of two nonnegative first powers in more ways than any smaller number (although admittedly ''all'' nonnegative integers share this property). 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$. Erdős proved in his 1956 paper that
:
for some constant $k$; in the other direction, Alford, Granville and Pomerance proved in their 1994 paper that
:$C(X)\; >\; X^\{2/7\}$
for sufficiently large $X$ and Glyn Harman proved that
:$C(X)\; >\; X^\{0.332\},$
again for sufficiently large $X$.^[3] This author has subsequently
improved the exponent to just over $1/3$. Erdős also gave a heuristic suggesting that his upper bound should be close to the true rate of growth of $C(X)$.
The distribution of Carmichael numbers by powers of 10, from Pinch (2006).

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

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 ''n''th-power-raising function ''p''_''n'' 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 ''p''_''n'' be an algebra endomorphism of 'Z'_''n''.
As above, ''p''_''n'' satisfies the same property whenever ''n'' is prime.
The ''n''th-power-raising function ''p''_''n'' is also defined on any 'Z'_''n''-algebra 'A'. A theorem states that ''n'' is prime if and only if all such functions ''p''_''n'' 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.^[4]
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.

References

1. Richard Pinch, "The Carmichael numbers up to 10¹⁸", April 2006 (building on his earlier work [1][2][3]).
2. W. R. Alford, A. Granville, and C. Pomerance. "There are Infinitely Many Carmichael Numbers." ''Annals of Mathematics'' '139' (1994) 703-722.
3. Glyn Harman. "On the number of Carmichael numbers up to X." ''Bull. Lond. Math. Soc.'' '37' (2005) 641-650.
4. Everett W. Howe. "Higher-order Carmichael numbers." ''Mathematics of Computation'' '69' (2000), pp. 1711–1719.


★ Chernick, J. (1935). On Fermat's simple theorem. ''Bull. Amer. Math. Soc.'' '45', 269–274.

★ Ribenboim, Paolo (1996). ''The New Book of Prime Number Records''.

★ Löh, Günter and Niebuhr, Wolfgang (1996). ''A new algorithm for constructing large Carmichael numbers''(pdf)

★ Korselt (1899). Probleme chinois. ''L'intermediaire des mathematiciens'', '6', 142–143.

★ Carmichael, R. D. (1912) On composite numbers P which satisfy the Fermat congruence . ''Am. Math. Month.'' '19' 22–27.

★ Erdős, Paul (1956). On pseudoprimes and Carmichael numbers, ''Publ. Math. Debrecen'' '4', 201 –206.

External links

★ Table of Carmichael numbers

★ Mathpages: The Dullness of 1729

★

★ Final Answers Modular Arithmetic