A Carmichael number is a composite number named after the mathematician Robert Daniel Carmichael. A Carmichael number divides for every integer . A Carmichael number c also satisfies the congruence , if . The first few Carmichael numbers are 561, 1105, 1729, 2465, 2821, 6601 and 8911. In 1994 Pomerance, Alford and Granville proved that there exist infinitely many Carmichael numbers.
- Every Carmichael number is square-free and has at least three different prime factors
- For every Carmichael number c it holds that is divisible by for every one of its prime factors .
- Every absolute Euler pseudoprime is a Carmichael number.
Chernick's Carmichael numbers
J. Chernick found in 1939 a way to construct Carmichael numbers . If, for a natural number n, the three numbers , and are prime numbers, the product is a Carmichael number. This condition can only be satisfied if the number ends with 0, 1, 5 or 6. An equivalent formulation of Chernick's construction is that if , and are prime numbers, then the product is a Carmichael number.
This way to construct Carmichael numbers may be extended to
with the condition that each of the factors is prime and that is divisible by .
Distribution of Carmichael numbers
Let C(X) denote the number of Carmichael numbers less than or equal to X. Then for all sufficiently large X
The upper bound is due to Erdős(1956) and Pomerance, Selfridge and Wagstaff (1980) and the lower bound is due to Glyn Harman (2005), improving the earlier lower bound of obtained by Alford, Granville and Pomerance (1994), which first established that there were infinitely many Carmichael numbers.. The asymptotic rate of growth of C(X) is not known.
References and notes
- J. Chernick, "On Fermat's simple theorem", Bull. Amer. Math. Soc. 45 (1939) 269-274
- (2003-11-22) Generic Carmichael Numbers
- Paulo Ribenboim, The new book of prime number records, Springer-Verlag (1996) ISBN 0-387-94457-5. P.120
- Paul Erdős, "On pseudoprimes and Carmichael numbers", Publ. Math. Debrecen 4 (1956) 201-206. MR 18 18
- C. Pomerance, J.L. Selfridge and S.S. Wagstaff jr, "The pseudoprimes to 25.109", Math. Comp. 35 (1980) 1003-1026. MR 82g:10030
- Glyn Harman (2005). "On the number of Carmichael numbers up to x". Bulletin of the London Mathematical Society 37: 641–650. DOI:10.1112/S0024609305004686. Zbl. 1108.11065. Research Blogging.
- W. R. Alford, A. Granville, and C. Pomerance (1994). "There are Infinitely Many Carmichael Numbers". Annals of Mathematics 139: 703-722. MR 95k:11114 Zbl 0816.11005.
- Richard Guy (2004). Unsolved problems in Number Theory, 3rd. Springer-Verlag. ISBN 0-387-20860-7. . Section A13