Carmichael number

Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
Citable Version  [?]
Code [?]

This editable Main Article is under development and subject to a disclaimer.

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

Properties

• Every Carmichael number is square-free and has at least three different prime factors
• For every Carmichael number c it holds that ${\displaystyle c-1}$ is divisible by ${\displaystyle p_{n}-1}$ for every one of its prime factors ${\displaystyle p_{n}}$.
• Every absolute Euler pseudoprime is a Carmichael number.

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 ${\displaystyle \scriptstyle 6n+1\ }$, ${\displaystyle \scriptstyle 12n+1\ }$ and ${\displaystyle \scriptstyle 18n+1\ }$ are prime numbers, the product ${\displaystyle \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 ${\displaystyle n\ }$ ends with 0, 1, 5 or 6. An equivalent formulation of Chernick's construction is that if ${\displaystyle \scriptstyle m\ }$, ${\displaystyle \scriptstyle 2m-1\ }$ and ${\displaystyle \scriptstyle 3m-2}$ are prime numbers, then the product ${\displaystyle \scriptstyle m\cdot (2m-1)\cdot (3m-2)}$ is a Carmichael number.

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

${\displaystyle 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 ${\displaystyle n\ }$ is divisible by ${\displaystyle 2^{k-4}}$.

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

${\displaystyle X^{0.332}

The upper bound is due to Erdős(1956)[4] and Pomerance, Selfridge and Wagstaff (1980)[5] and the lower bound is due to Glyn Harman (2005),[6] improving the earlier lower bound of ${\displaystyle X^{2/7}}$ obtained by Alford, Granville and Pomerance (1994), which first established that there were infinitely many Carmichael numbers.[7]. The asymptotic rate of growth of C(X) is not known.[8]

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. 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.
7. 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.
8. Richard Guy (2004). Unsolved problems in Number Theory, 3rd. Springer-Verlag. ISBN 0-387-20860-7. . Section A13