Carmichael number
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000:
The hardware and software on this system was updated September 4th.  Please let me know of any problem you encounter. <caldwell@utm.edu>

The composite integer n is a Carmichael number if an-1=1 (mod n) for every integer a relatively prime to n. (This condition is satisfied by all primes because of Fermat's Little Theorem.) The Fermat probable primality test will fail to show a Carmichael number is composite until we run across one of its factors!

The Carmichael numbers under 100,000 are

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, and 75361.
Small Carmichael numbers are rare: there are only 2,163 are less than 25,000,000,000. (Recently, Richard Pinch has found that there are still only 246,683 Carmichael numbers below 10,000,000,000,000,000.) Nevertheless, in 1994 it was proved that there are infinitely many of them!

See Also: Pseudoprime, PRP

Related pages (outside of this work)

References:

AGP94 (Infinitely many Carmichael numbers)
W. R. Alford, A. Granville and C. Pomerance, "There are infinitely many Carmichael numbers," Ann. of Math. (2), 139 (1994) 703--722.  MR 95k:11114
GP2001
A. Granville and C. Pomerance, "Two contradictory conjectures concerning Carmichael numbers," Math. Comp., 71 (2002) 883--908.  MR 1 885 636 (Abstract available)
Pinch93
R. Pinch, "The Carmichael numbers up to 1015," Math. Comp., 61:203 (1993) 381-391.  MR 93m:11137 [A preprint and several data files may be found in the Carmichael directory of his FTP site. For example, he lists the Carmichaels to 1017.]



Chris K. Caldwell © 1999-2014 (all rights reserved)