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, aN 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):
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):
Properties
| 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 Nth-power-raising function pN from the ring ZN of integers modulo N to itself is the identity function. The identity is the only ZN-algebra endomorphism on ZN so we can restate the definition as asking that pN be an algebra endomorphism of ZN.
As above, pN satisfies the same property whenever N is prime.
The Nth-power-raising function pN is also defined on any ZN-algebra A. A theorem states that N is prime if and only if all such functions pN 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 pN is an endomorphism on every ZN-algebra that can be generated as ZN-module by m elements. Carmichael numbers of order 1 are just the ordinary Carmichael numbers.
Korselt's criterion can be generalized to higher-order Carmichael numbers, see Howe's paper listed below.
A heuristic argument, given in the same paper, appears to suggest that there are infinitely many Carmichael numbers of order m, for any m. However, not a single Carmichael number of order 3 or above is known.
Higher-order Carmichael numbers
Properties
References and External links