- Carmichael number
In

number theory , a**Carmichael number**is a composite positiveinteger $n$ which satisfies thecongruence $b^\{n-1\}~equiv\; 1\; pmod\{n\}$ for all integers $b$ which arerelatively prime to $n$ (seemodular arithmetic ). They are named for Robert Carmichael. The Carmichael numbers are theKnödel number s "K"_{1}.**Overview**Fermat's little theorem states that allprime numbers have that property. In this sense, Carmichael numbers are similar to prime numbers. They are called Fermatpseudoprime s. 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

^{18}(approximately one in 700 billion numbers.) [*Richard Pinch, [*] This makes tests based on Fermat's Little Theorem slightly risky compared to others such as the*http://arxiv.org/abs/math/0604376 "The Carmichael numbers up to 10*] , April 2006 (building on his earlier work [^{18}"*http://www.chalcedon.demon.co.uk/rgep/p37.ps*] [*http://arxiv.org/abs/math.NT/9803082*] [*http://arxiv.org/abs/math.NT/0504119*] ).Solovay-Strassen primality test .An alternative and equivalent definition of Carmichael numbers is given by

**Korselt's criterion**.**Theorem**(Korselt 1899): A positive composite integer $n$ is a Carmichael number if and only if $n$ is square-free, and for allprime divisor s $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 criterion. Indeed, $561\; =\; 3\; cdot\; 11\; cdot\; 17$ is squarefree and $2\; |\; 560$, $10\; |\; 560$ and $16\; |\; 560$.

The next few Carmichael numbers are OEIS|id=A002997::$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)$

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. Whether this formula produces an infinite quantity of Carmichael numbers is an open question.Paul Erdős heuristically argued there should be infinitely many Carmichael numbers. In 1994 it was shown byW. R. (Red) Alford ,Andrew Granville andCarl 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$. [*W. R. Alford, A. Granville, and C. Pomerance. [*]*http://www.math.dartmouth.edu/~carlp/PDF/paper95.pdf "There are Infinitely Many Carmichael Numbers."*] "Annals of Mathematics"**139**(1994) 703-722.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 OEIS|id=A006931:

As of December 2007, it has been shown that there are 8220777 Carmichael numbers up to 10

^{20}.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$. [

*Glyn Harman. "On the number of Carmichael numbers up to X." "Bull. Lond. Math. Soc."*] This author has subsequentlyimproved the exponent to just over $1/3$. Erds also gave a heuristic suggesting that his upper bound should be close to the true rate of growth of $C(X)$.**37**(2005) 641-650.The distribution of Carmichael numbers by powers of 10, from Pinch (2006).

**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"}-algebraendomorphism 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. [

*Everett W. Howe. [*]*http://arxiv.org/abs/math.NT/9812089 "Higher-order Carmichael numbers."*] "Mathematics of Computation"**69**(2000), pp. 1711–1719.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*** 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). [*http://www.ams.org/mcom/1996-65-214/S0025-5718-96-00692-8/S0025-5718-96-00692-8.pdf "A new algorithm for constructing large Carmichael numbers"*] (pdf)

* Korselt (1899). Problème chinois. "L'intermédiaire des mathématiciens",**6**, 142–143.

* Carmichael, R. D. (1912) On composite numbers P which satisfy the Fermat congruence $a^\{P-1\}equiv\; 1mod\; P$. "Am. Math. Month."**19**22–27.

* Erdős, Paul (1956). On pseudoprimes and Carmichael numbers, "Publ. Math. Debrecen"**4**, 201 –206.**External links*** [

*http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Carmichael-Zahlen Table of Carmichael numbers*]

* [*http://www.mathpages.com/home/kmath028.htm Mathpages: The Dullness of 1729*]

*

* [*http://www.numericana.com/answer/modular.htm Final Answers Modular Arithmetic*]

* Richard G.E. Pinch. The Carmichael numbers up to 10 to the 20. [*http://www.chalcedon.demon.co.uk/rgep/rcam.html (list of publications)*]

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Lucas-Carmichael number**— In mathematics, a Lucas Carmichael number is a positive integer n such that if p is a prime factor of n , then p + 1 is a factor of n + 1. By convention, a number is only regarded as a Lucas Carmichael number if it is odd and square free (not… … Wikipedia**Carmichael**— is a Scottish clan, from the village of Carmichael, in South Lanarkshire, Scottish Lowlands, United Kingdom. It is also the name of a family from the west coast of Scotland, from the Gaelic MacGillemichael, meaning son of the servant of Michael,… … Wikipedia**Carmichael-Zahl**— Eine natürliche Zahl heißt Carmichael Zahl, benannt nach dem Mathematiker Robert Daniel Carmichael, wenn sie eine fermatsche Pseudoprimzahl bezüglich aller zu ihr teilerfremden Basen ist. Carmichael Zahlen spielen eine Rolle bei der Analyse von… … Deutsch Wikipedia**Carmichael function**— In number theory, the Carmichael function of a positive integer n, denoted lambda(n),is defined as the smallest positive integer m such that:a^m equiv 1 pmod{n}for every integer a that is coprime to n.In other words, in more algebraic terms, it… … Wikipedia**Carmichael**— CARMICHAEL, a parish, in the Upper ward of the county of Lanark, 5 miles (S. E.) from Lanark, containing 874 inhabitants. This place derives its name from St. Michael, to whom its first church was dedicated. The remains of antiquity of which… … A Topographical dictionary of Scotland**Carmichael's totient function conjecture**— In mathematics, Carmichael s totient function conjecture concerns the multiplicity of values of Euler s totient function phi;( n ), which counts the number of integers less than and coprime to n .This function phi;( n ) is equal to 2 when n is… … Wikipedia**Carmichael's theorem**— This article refers to Carmichael s theorem about Fibonacci numbers. Carmichael s theorem may also refer to the recursive definition of the Carmichael function. Carmichael s theorem, named after the American mathematician R.D. Carmichael, states… … Wikipedia**Carmichael, Stokely**— ▪ 1999 Trinidadian born civil rights leader and black nationalist (b. June 29, 1941, Port of Spain, Trinidad d. Nov. 15, 1998, Conakry, Guinea), originated the slogan black power, urged African Americans in the United States to abandon… … Universalium**10000 (number)**— Number number = 10000 prev = 9999 next = 100000 range = 10000 100000 cardinal = 10000 ordinal = th ordinal text = ten thousandth numeral = decamillesimal factorization = 2^4 cdot 5^4 prime = divisor = roman = overline|X unicode = overline|X, ↂ… … Wikipedia**40000 (number)**— Number number = 40000 range = 10000 100000 cardinal = 40000 ordinal = th ordinal text = thirty thousandth factorization = 2^6 cdot 5^4 bin = 1001110001000000 oct = 116100 hex = 9C4040,000 (forty thousand) is the number that comes after 39,999 and … Wikipedia