Namespaces
Variants
Actions

Difference between revisions of "Carmichael number"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(Category:Number theory)
 
(11 intermediate revisions by 4 users not shown)
Line 1: Line 1:
A composite natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c1101001.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c1101002.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c1101003.png" />, whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c1101004.png" /> is relatively prime to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c1101005.png" />. Thus they are pseudo-primes (cf. [[Pseudo-prime|Pseudo-prime]]) for every such base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c1101006.png" />. These numbers play a role in the theory of probabilistic primality tests (cf. [[Probabilistic primality test|Probabilistic primality test]]), as they show that Fermat's theorem, to wit <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c1101007.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c1101008.png" />, whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c1101009.png" /> is prime and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010010.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010011.png" />, is not a sufficient criterion for primality (cf. also [[Fermat little theorem|Fermat little theorem]]).
+
{{TEX|done}}
 +
 
 +
 
 +
A composite natural number $n$ for which $a^{n-1} \equiv 1 \pmod{n}$ whenever $a$ is relatively prime to $n$. Thus they are pseudo-primes (cf. [[Pseudo-prime|Pseudo-prime]]) for every such base $a$. These numbers play a role in the theory of probabilistic primality tests (cf. [[Probabilistic primality test|Probabilistic primality test]]), as they show that Fermat's theorem, to wit $ a^p \equiv a \pmod{p}$, whenever $p$ is prime and $a \not\equiv 0 \pmod{p}$, is not a sufficient criterion for primality (cf. also [[Fermat little theorem|Fermat little theorem]]).
  
 
The first five Carmichael numbers are
 
The first five Carmichael numbers are
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010012.png" /></td> </tr></table>
+
\[561,\ 1105,\ 1729,\ 2465,\ 2821 \]
 +
 
 +
R.D. Carmichael [[#References|[a2]]] characterized them as follows. Let $\lambda(n)$ be the exponent of the multiplicative group of integers modulo $n$, that is, the least positive $\lambda$ making all $\lambda$-th powers in the group equal to $1$. (This is readily computed from the prime factorization of $n$.) Then a composite natural number $n$ is Carmichael if and only if $\lambda(n) \mid n-1$. From this it follows that every Carmichael number is odd, square-free, and has at least $3$ distinct prime factors.
  
R.D. Carmichael [[#References|[a2]]] characterized them as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010013.png" /> be the exponent of the multiplicative group of integers modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010014.png" />, that is, the least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010015.png" /> making all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010016.png" />th powers in the group equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010017.png" />. (This is readily computed from the prime factorization of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010018.png" />.) Then a composite natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010019.png" /> is Carmichael if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010020.png" />. From this it follows that every Carmichael number is odd, square-free, and has at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010021.png" /> distinct prime factors.
+
Let $C(x)$ denote the number of Carmichael numbers $\le x$. W.R. Alford, A. Granville and C. Pomerance [[#References|[a1]]] proved that $C(x) > x^{2/7}$ for sufficiently large $x$. This settled a long-standing conjecture that there are infinitely many Carmichael numbers. It is believed on probabilistic grounds that $\log C(x) \sim \log x$. [[#References|[a4]]].
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010022.png" /> denote the number of Carmichael numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010023.png" />. W.R. Alford, A. Granville and C. Pomerance [[#References|[a1]]] proved that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010024.png" /> for sufficiently large <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010025.png" />. This settled a long-standing conjecture that there are infinitely many Carmichael numbers. It is believed on probabilistic grounds that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010026.png" /> [[#References|[a4]]].
+
P. Erdős proved in 1956 that $ C(X) < X \exp(- k \log X \log\log\log X / \log\log X) $ for some constant $ k $: he also gave a heuristic suggesting that his upper bound should be close to the true rate of growth of $ C(X) $.[[#References|[a5]]]
  
There is apparently no better way to compute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010027.png" /> than to make a list of the Carmichael numbers up to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010028.png" />. The most exhaustive computation to date (1996) is that of R.G.E. Pinch, who used the methods of [[#References|[a3]]] to determine that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010029.png" />.
+
There is apparently no better way to compute $C(x)$ than to make a list of the Carmichael numbers up to $x$. The most exhaustive computation to date (1996) is that of R.G.E. Pinch, who used the methods of [[#References|[a3]]] to determine that $C\left({10^{16}}\right) = 246,683$.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W.R. Alford,  A. Granville,  C. Pomerance,  "There are infinitely many Carmichael numbers"  ''Ann. of Math.'' , '''140'''  (1994)  pp. 703–722</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.D. Carmichael,  "Note on a new number theory function"  ''Bull. Amer. Math. Soc.'' , '''16'''  (1910)  pp. 232–238  (See also: Amer. Math. Monthly 19 (1912), 22–27)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.G.E. Pinch,  "The Carmichael numbers up to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010030.png" />"  ''Math. Comp.'' , '''61'''  (1993)  pp. 381–391</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  C. Pomerance,  J.L. Selfridge,  S.S. Wagstaff, Jr.,  "The pseudoprimes to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110100/c11010031.png" />" ''Math. Comp.'' , '''35''' (1980) pp. 1003–1026</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  W.R. Alford,  A. Granville,  C. Pomerance,  "There are infinitely many Carmichael numbers"  ''Ann. of Math.'' , '''140'''  (1994)  pp. 703–722</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  R.D. Carmichael,  "Note on a new number theory function"  ''Bull. Amer. Math. Soc.'' , '''16'''  (1910)  pp. 232–238  (See also: Amer. Math. Monthly 19 (1912), 22–27)</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  R.G.E. Pinch,  "The Carmichael numbers up to $10^{15}$"  ''Math. Comp.'' , '''61'''  (1993)  pp. 381–391</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  C. Pomerance,  J.L. Selfridge,  S.S. Wagstaff, Jr.,  "The pseudoprimes to $25.10^9$"  ''Math. Comp.'' , '''35'''  (1980)  pp. 1003–1026</TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top"> P. Erdős, "On pseudoprimes and Carmichael numbers" ''Publ. Math. Debrecen'', '''4''' (1956) pp.201–206.</TD></TR>
 +
</table>
 +
 
 +
[[Category:Number theory]]

Latest revision as of 17:34, 18 October 2014


A composite natural number $n$ for which $a^{n-1} \equiv 1 \pmod{n}$ whenever $a$ is relatively prime to $n$. Thus they are pseudo-primes (cf. Pseudo-prime) for every such base $a$. These numbers play a role in the theory of probabilistic primality tests (cf. Probabilistic primality test), as they show that Fermat's theorem, to wit $ a^p \equiv a \pmod{p}$, whenever $p$ is prime and $a \not\equiv 0 \pmod{p}$, is not a sufficient criterion for primality (cf. also Fermat little theorem).

The first five Carmichael numbers are

\[561,\ 1105,\ 1729,\ 2465,\ 2821 \]

R.D. Carmichael [a2] characterized them as follows. Let $\lambda(n)$ be the exponent of the multiplicative group of integers modulo $n$, that is, the least positive $\lambda$ making all $\lambda$-th powers in the group equal to $1$. (This is readily computed from the prime factorization of $n$.) Then a composite natural number $n$ is Carmichael if and only if $\lambda(n) \mid n-1$. From this it follows that every Carmichael number is odd, square-free, and has at least $3$ distinct prime factors.

Let $C(x)$ denote the number of Carmichael numbers $\le x$. W.R. Alford, A. Granville and C. Pomerance [a1] proved that $C(x) > x^{2/7}$ for sufficiently large $x$. This settled a long-standing conjecture that there are infinitely many Carmichael numbers. It is believed on probabilistic grounds that $\log C(x) \sim \log x$. [a4].

P. Erdős proved in 1956 that $ C(X) < X \exp(- k \log X \log\log\log X / \log\log X) $ for some constant $ k $: he also gave a heuristic suggesting that his upper bound should be close to the true rate of growth of $ C(X) $.[a5]

There is apparently no better way to compute $C(x)$ than to make a list of the Carmichael numbers up to $x$. The most exhaustive computation to date (1996) is that of R.G.E. Pinch, who used the methods of [a3] to determine that $C\left({10^{16}}\right) = 246,683$.

References

[a1] W.R. Alford, A. Granville, C. Pomerance, "There are infinitely many Carmichael numbers" Ann. of Math. , 140 (1994) pp. 703–722
[a2] R.D. Carmichael, "Note on a new number theory function" Bull. Amer. Math. Soc. , 16 (1910) pp. 232–238 (See also: Amer. Math. Monthly 19 (1912), 22–27)
[a3] R.G.E. Pinch, "The Carmichael numbers up to $10^{15}$" Math. Comp. , 61 (1993) pp. 381–391
[a4] C. Pomerance, J.L. Selfridge, S.S. Wagstaff, Jr., "The pseudoprimes to $25.10^9$" Math. Comp. , 35 (1980) pp. 1003–1026
[a5] P. Erdős, "On pseudoprimes and Carmichael numbers" Publ. Math. Debrecen, 4 (1956) pp.201–206.
How to Cite This Entry:
Carmichael number. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Carmichael_number&oldid=15179
This article was adapted from an original article by E. Bach (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article