A positive integer *N* is called a **Carmichael number** if and only if *N* is composite and for all integers *a* which are relatively prime to *N*, *a*^{N} is congruent to *a* modulo *N* (see modular arithmetic).

Fermat's little theorem states that all prime numbers have this property. In this sense, Carmichael numbers are similar to prime numbers. They are called pseudoprimes. Carmichael numbers are sometimes also called *absolute pseudoprimes*.

Carmichael numbers are important because they can fool the Fermat primality test. If Carmichael numbers did not exist this primality test could always be used to prove compositeness of a number. Fortunately as numbers become larger Carmichael numbers become rarer.

An alternative and equivalent definition of Carmichael numbers is given by Korselt's theorem from 1899.

Theorem (Korselt): A positive and odd integer *N* is a Carmichael number if and only if *N* is square-free, and for all prime divisors *p* of *N*, *p*-1 divides *N*-1.

It follows from this theorem that Carmichael numbers are always odd.

Korselt was the first who observed these properties, but he could not find an example. In 1910 Robert Daniel Carmichael found the first and smallest such number, 561, and hence the name.

That 561 is a Carmichael number can be seen with Korselt's theorem. Indeed, 561 = 3 · 11 · 17 is squarefree and 2 | 560, 10 | 560 and 16 | 560. The next Carmichael numbers are (SIDN A002997):

- 1105 = 5 · 13 · 17 (4 | 1104, 12 | 1104, 16 | 1104),
- 1729 = 7 · 13 · 19 (6 | 1728, 12 | 1728, 18 | 1728),
- 2465 = 5 · 17 · 29 (4 | 2464, 16 | 2464, 28 | 2464),
- 2821 = 7 · 13 · 31 (6 | 2820, 12 | 2820, 30 | 2820),
- 6601 = 7 · 23 · 41 (6 | 6600, 22 | 6600, 40 | 6600),
- 8911 = 7 · 19 · 67 (6 | 8910, 18 | 8910, 66 | 8910),
- ...

Paul Erdös heuristically argued there should be infinitely many Carmichael numbers. In 1994 it was shown by William Alford, Andrew Granville and Carl Pomerance that there really exist infinitely many Carmichael numbers. Richard G. E. Pinch also gave and proved an upper bound for *C*(*n*), the number of Carmichael numbers less than *n*.

Table of contents |

2 Higher-order Carmichael numbers 3 Properties 4 References and External links |

Carmichael numbers have at least three positive prime factors. The first Carmichael numbers with *k*= 3, 4, 5, ... prime factors are (SIDN A006931):

k | |
---|---|

3 | 561 = 3 · 11 · 17 |

4 | 41041 = 7 · 11 · 13 · 41 |

5 | 825265 = 5 · 7 · 17 · 19 · 73 |

6 | 321197185 = 5 · 19 · 23 · 29 · 37 · 137 |

7 | 5394826801 = 7 · 13 · 17 · 23 · 31 · 67 · 73 |

8 | 232250619601 = 7 · 11 · 13 · 17 · 31 · 37 · 73 · 163 |

9 | 9746347772161 = 7 · 11 · 13 · 17 · 19 · 31 · 37 · 41 · 641 |

The first Carmichael numbers with 4 prime factors are:

n | |
---|---|

1 | 41041 = 7 · 11 · 13 · 41 |

2 | 62745 = 3 · 5 · 47 · 89 |

3 | 63973 = 7 · 13 · 19 · 37 |

4 | 75361 = 11 · 13 · 17 · 31 |

5 | 101101 = 7 · 11 · 13 · 101 |

6 | 126217 = 7 · 13 · 19 · 73 |

7 | 172081 = 7 · 13 · 31 · 61 |

8 | 188461 = 7 · 13 · 19 · 109 |

9 | 278545 = 5 · 17 · 29 · 113 |

10 | 340561 = 13 · 17 · 23 · 67 |

Carmichael numbers can be generalized using concepts of abstract algebra.

The above definition states that a composite integer *N* is Carmichael
precisely when the *N*th-power-raising function *p*_{N} from the ring **Z**_{N} of integers modulo *N* to itself is the identity function. The identity is the only **Z**_{N}-algebra endomorphism on **Z**_{N} so we can restate the definition as asking that *p*_{N} be an algebra endomorphism of **Z**_{N}.
As above, *p*_{N} satisfies the same property whenever *N* is prime.

The *N*th-power-raising function *p*_{N} is also defined on any **Z**_{N}-algebra **A**. A theorem states that *N* is prime if and only if all such functions *p*_{N} are algebra endomorphisms.

In-between these two conditions lies the definition of **Carmichael number of order m** for any positive integer *m* as any composite number *N* such that *p*_{N} is an endomorphism on every **Z**_{N}-algebra that can be generated as **Z**_{N}-module by *m* elements. Carmichael numbers of order 1 are just the ordinary Carmichael numbers.

- Everett W. Howe,
*Higher-order Carmichael numbers*Math. Comp. 69 (2000) p. 1711-1719, " class="external">http://arxiv.org/abs/math.NT/9812089 - J. Chernick,
*On Fermat's simple theorem*, Bull. Amer. Math. Soc., 45 (1935), p. 269-274.