Carmichael number

From Knowino
Jump to: navigation, search

A Carmichael number is a composite number named after the mathematician Robert Daniel Carmichael. A Carmichael number \scriptstyle c\ divides \scriptstyle a^c - a\ for every integer \scriptstyle a\ . A Carmichael number c also satisfies the congruence \scriptstyle a^{c-1} \equiv 1 \pmod c, if \scriptstyle \operatorname{gcd}(a,c) = 1. 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.


[edit] Properties

[edit] Chernick's Carmichael numbers

J. Chernick found in 1939 a way to construct Carmichael numbers[1] [2]. If, for a natural number n, the three numbers \scriptstyle 6n+1\ , \scriptstyle 12n+1\ and \scriptstyle 18n+1\ are prime numbers, the product \scriptstyle M_3(n) = (6n+1)\cdot (12n+1)\cdot (18n+1) is a Carmichael number. This condition can only be satisfied if the number n\ ends with 0, 1, 5 or 6. An equivalent formulation of Chernick's construction is that if \scriptstyle m\ , \scriptstyle 2m-1\ and \scriptstyle 3m-2 are prime numbers, then the product \scriptstyle m\cdot (2m-1)\cdot (3m-2) is a Carmichael number.

This way to construct Carmichael numbers may be extended[3] to

M_k(n)=(6n+1)(12n+1)\prod_{i=1}^{k-2}(9\cdot 2^i n+1) \,

with the condition that each of the factors is prime and that n\ is divisible by 2k − 4.

[edit] 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

X^{2/7} < C(X) < X \exp(-\log X \log\log\log X / \log\log X) . \,

The upper bound is due to Erdős(1956)[4] and Pomerance, Selfridge and Wagstaff (1980)[5] and the lower bound is due to Alford, Granville and Pomerance (1994)[6]. The asymptotic rate of growth of C(X) is not known.[7]

[edit] References and notes

  1. J. Chernick, "On Fermat's simple theorem", Bull. Amer. Math. Soc. 45 (1939) 269-274
  2. (2003-11-22) Generic Carmichael Numbers
  3. Paulo Ribenboim, The new book of prime number records, Springer-Verlag (1996) ISBN 0-387-94457-5. P.120
  4. Paul Erdős, "On pseudoprimes and Carmichael numbers", Publ. Math. Debrecen 4 (1956) 201-206. MR 18 18
  5. C. Pomerance, J.L. Selfridge and S.S. Wagstaff jr, "The pseudoprimes to 25.109", Math. Comp. 35 (1980) 1003-1026. MR 82g:10030
  6. W. R. Alford, A. Granville, and C. Pomerance. "There are Infinitely Many Carmichael Numbers", Annals of Mathematics 139 (1994) 703-722. MR 95k:11114
  7. Richard Guy, "Unsolved problems in Number Theory" (3rd ed), Springer-Verlag (2004) ISBN 0-387-20860-7. Section A13
Information.svg Some content on this page may previously have appeared on Citizendium.
Personal tools