# Difference between revisions of "Carmichael number"

A composite natural number for which modulo , whenever is relatively prime to . Thus they are pseudo-primes (cf. Pseudo-prime) for every such base . 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 , whenever is prime and modulo , is not a sufficient criterion for primality (cf. also Fermat little theorem).

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

Let denote the number of Carmichael numbers . W.R. Alford, A. Granville and C. Pomerance [a1] proved that for sufficiently large . This settled a long-standing conjecture that there are infinitely many Carmichael numbers. It is believed on probabilistic grounds that [a4].

There is apparently no better way to compute than to make a list of the Carmichael numbers up to . The most exhaustive computation to date (1996) is that of R.G.E. Pinch, who used the methods of [a3] to determine that .

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