# Carmichael number

From Encyclopedia of Mathematics

A composite natural number $n$ for which $a^{n-1} \equiv 1$ modulo $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$ modulo $p$, whenever $p$ is prime and $a \not\equiv 0$ modulo $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 "  Math. Comp. , 61  (1993)  pp. 381–391
[a4]  C. Pomerance,   J.L. Selfridge,   S.S. Wagstaff, Jr.,   "The pseudoprimes to "  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://www.encyclopediaofmath.org/index.php?title=Carmichael_number&oldid=29473
This article was adapted from an original article by E. Bach (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 32, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8775172829627991, "perplexity_flag": "middle"}