Carmichael Number

A Carmichael number is an Odd Composite Number $n$ which satisfies Fermat's Little Theorem

$$a^{n-1}-1\equiv 0\ \left({{\rm mod\ } {n}}\right)$$

for every choice of $a$ satisfying $(a,n)=1$ (i.e., $a$ and $n$ are Relatively Prime) with $1<a<n$. A Carmichael number is therefore a Pseudoprimes to any base. Carmichael numbers therefore cannot be found to be Composite using Fermat's Little Theorem. However, if $(a,n)\not=1$, the congruence of Fermat's Little Theorem is sometimes Nonzero, thus identifying a Carmichael number $n$ as Composite.

Carmichael numbers are sometimes called Absolute Pseudoprimes and also satisfy Korselt's Criterion. R. D. Carmichael first noted the existence of such numbers in 1910, computed 15 examples, and conjectured that there were infinitely many (a fact finally proved by Alford et al. 1994).

The first few Carmichael numbers are 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, ... (Sloane's A002997). Carmichael numbers have at least three Prime Factors. For Carmichael numbers with exactly three Prime Factors, once one of the Primes has been specified, there are only a finite number of Carmichael numbers which can be constructed. Numbers of the form $(6k+1)(12k+1)(18k+1)$ are Carmichael numbers if each of the factors is Prime (Korselt 1899, Ore 1988, Guy 1994). This can be seen since for

$$N\equiv (6k+1)(12k+1)(18k+1)=1296k^3+396k^2+36k+1,$$

$N-1$ is a multiple of $36k$ and the Least Common Multiple of $6k$, $12k$, and $18k$ is $36k$, so $a^{N-1}\equiv 1$ modulo each of the Primes $6k+1$, $12k+1$, and $18k+1$, hence $a^{N-1}\equiv 1$ modulo their product. The first few such Carmichael numbers correspond to $k=1$, 6, 35, 45, 51, 55, 56, ... (Sloane's A046025) and are 1729, 294409, 56052361, 118901521, ... (Sloane's A033502). The largest known Carmichael number of this form was found by H. Dubner in 1996 and has 1025 digits.

The smallest Carmichael numbers having 3, 4, ... factors are $561=3\times 11\times 17$, $41041=7\times 11\times 13\times 41$, 825265, 321197185, ... (Sloane's A006931). In total, there are only 43 Carmichael numbers $<10^6$, 2163 $\leq 2.5\times 10^{10}$, 105,212 $\leq 10^{15}$, and 246,683 $\leq 10^{16}$ (Pinch 1993). Let $C(n)$ denote the number of Carmichael numbers less than $n$. Then, for sufficiently large $n$ ($n\sim 10^7$ from numerical evidence),

$$C(n) \sim n^{2/7}$$

(Alford et al. 1994).

The Carmichael numbers have the following properties:

1. If a Prime $p$ divides the Carmichael number $n$, then $n\equiv 1\ \left({{\rm mod\ } {p-1}}\right)$ implies that $n\equiv p\ \left({{\rm mod\ } {p(p-1)}}\right)$.

2. Every Carmichael number is Squarefree.

3. An Odd Composite Squarefree number $n$ is a Carmichael number Iff $n$ divides the Denominator of the Bernoulli Number $B_{n-1}$.

See also Carmichael Condition, Pseudoprime

References

Alford, W. R.; Granville, A.; and Pomerance, C. ``There are Infinitely Many Carmichael Numbers.'' Ann. Math. 139, 703-722, 1994.

Beyer, W. H. CRC Standard Mathematical Tables, 28th ed. Boca Raton, FL: CRC Press, p. 87, 1987.

Guy, R. K. ``Carmichael Numbers.'' §A13 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 30-32, 1994.

Korselt, A. ``Problème chinois.'' L'intermédiaire math. 6, 143-143, 1899.

Ore, Ø. Number Theory and Its History. New York: Dover, 1988.

Pinch, R. G. E. ``The Carmichael Numbers up to $10^{15}$.'' Math. Comput. 55, 381-391, 1993.

Pinch, R. G. E. ftp://emu.pmms.cam.ac.uk/pub/Carmichael/.

Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. Jr. ``The Pseudoprimes to $25\cdot 10^9$.'' Math. Comput. 35, 1003-1026, 1980.

Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Basel: Birkhäuser, pp. 89-90 and 94-95, 1994.

Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 116, 1993.

Sloane, N. J. A. Sequences A002997/M5462, A006931/M5463, A033502, and A046025 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.