In number theory, a Carmichael number is a composite number which in modular arithmetic satisfies the congruence relation:
bn\equivb\pmod{n}
bn-1\equiv1\pmod{n}
b
They constitute the comparatively rare instances where the strict converse of Fermat's Little Theorem does not hold. This fact precludes the use of that theorem as an absolute test of primality.[4]
The Carmichael numbers form the subset K1 of the Knödel numbers.
The Carmichael numbers were named after the American mathematician Robert Carmichael by Nicolaas Beeger, in 1950. Øystein Ore had referred to them in 1948 as numbers with the "Fermat property", or "F numbers" for short.[5]
Fermat's little theorem states that if
p
bp-b
b
However, no Carmichael number is either an Euler–Jacobi pseudoprime or a strong pseudoprime to every base relatively prime to it[6] so, in theory, either an Euler or a strong probable prime test could prove that a Carmichael number is, in fact, composite.
Arnault[7] gives a 397-digit Carmichael number
N
N=p ⋅ (313(p-1)+1) ⋅ (353(p-1)+1)
p=
p
As numbers become larger, Carmichael numbers become increasingly rare. For example, there are 20,138,200 Carmichael numbers between 1 and 1021 (approximately one in 50 trillion (5·1013) numbers).[8]
An alternative and equivalent definition of Carmichael numbers is given by Korselt's criterion.
Theorem (A. Korselt 1899): A positive composite integer
n
n
p
It follows from this theorem that all Carmichael numbers are odd, since any even composite number that is square-free (and hence has only one prime factor of two) will have at least one odd prime factor, and thus
p-1\midn-1
-1
The first seven Carmichael numbers, from 561 to 8911, were all found by the Czech mathematician Václav Šimerka in 1885[11] (thus preceding not just Carmichael but also Korselt, although Šimerka did not find anything like Korselt's criterion).[12] His work, published in Czech scientific journal Časopis pro pěstování matematiky a fysiky, however, remained unnoticed.
Korselt was the first who observed the basic properties of Carmichael numbers, but he did not give any examples.
That 561 is a Carmichael number can be seen with Korselt's criterion. Indeed,
561=3 ⋅ 11 ⋅ 17
10\mid560
1105=5 ⋅ 13 ⋅ 17 (4\mid1104; 12\mid1104; 16\mid1104)
1729=7 ⋅ 13 ⋅ 19 (6\mid1728; 12\mid1728; 18\mid1728)
2465=5 ⋅ 17 ⋅ 29 (4\mid2464; 16\mid2464; 28\mid2464)
2821=7 ⋅ 13 ⋅ 31 (6\mid2820; 12\mid2820; 30\mid2820)
6601=7 ⋅ 23 ⋅ 41 (6\mid6600; 22\mid6600; 40\mid6600)
8911=7 ⋅ 19 ⋅ 67 (6\mid8910; 18\mid8910; 66\mid8910).
In 1910, Carmichael himself[13] also published the smallest such number, 561, and the numbers were later named after him.
Jack Chernick[14] proved a theorem in 1939 which can be used to construct a subset of Carmichael numbers. The number
(6k+1)(12k+1)(18k+1)
Paul Erdős heuristically argued there should be infinitely many Carmichael numbers. In 1994 W. R. (Red) Alford, Andrew Granville and Carl Pomerance used a bound on Olson's constant to show that there really do exist infinitely many Carmichael numbers. Specifically, they showed that for sufficiently large
n
n2/7
Thomas Wright proved that if
a
m
Löh and Niebuhr in 1992 found some very large Carmichael numbers, including one with 1,101,518 factors and over 16 million digits.This has been improved to 10,333,229,505 prime factors and 295,486,761,787 digits,[16] so the largest known Carmichael number is much greater than the largest known prime.
Carmichael numbers have at least three positive prime factors. The first Carmichael numbers with
k=3,4,5,\ldots
| 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 :
| i | ||
|---|---|---|
| 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 |
The second Carmichael number (1105) can be expressed as the sum of two squares in more ways than any smaller number. The third Carmichael number (1729) is the Hardy-Ramanujan Number: the smallest number that can be expressed as the sum of two cubes (of positive numbers) in two different ways.
Let
C(X)
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
C(10n) | 0 | 0 | 1 | 7 | 16 | 43 | 105 | 255 | 646 | 1547 | 3605 | 8241 | 19279 | 44706 | 105212 | 246683 | 585355 | 1401644 | 3381806 | 8220777 | 20138200 |
C(X)<X\exp\left({-k1\left(logXloglog
| ||||
| X\right) |
In 1956, Erdős improved the bound to
C(X)<X\exp\left(
| -k2logXlogloglogX | |
| loglogX |
\right)
In the other direction, Alford, Granville and Pomerance proved in 1994 that for sufficiently large X,
C(X)>
| ||||
| X |
.
In 2005, this bound was further improved by Harman[18] to
C(X)>X0.332
Regarding the asymptotic distribution of Carmichael numbers, there have been several conjectures. In 1956, Erdős[17] conjectured that there were
X1-o(1)
X ⋅ L(X)-1
However, inside current computational ranges (such as the counts of Carmichael numbers performed by Pinch[8] up to 1021), these conjectures are not yet borne out by the data.
In 2021, Daniel Larsen proved an analogue of Bertrand's postulate for Carmichael numbers first conjectured by Alford, Granville, and Pomerance in 1994.[21] Using techniques developed by Yitang Zhang and James Maynard to establish results concerning small gaps between primes, his work yielded the much stronger statement that, for any
\delta>0
x
\delta
| \exp{\left( | log{x |
x
| x+ | x |
| (log{x |
| ||||
| ) |
akp
\alpha{\rm(akp)}\equiv\alpha\bmod{akp}
\alpha
{\rmN}(akp)
mp\equivm\bmodp
aka
{lO}K
\alpha{\rm(aka)}\equiv\alpha\bmod{aka}
{\rmN}(aka)
aka
aka=(a)
When is larger than the rationals it is easy to write down Carmichael ideals in : for any prime number that splits completely in, the principal ideal
p{lO}K
Z[i]
Both prime and Carmichael numbers satisfy the following equality:
\gcd
| n-1 | |
| \left(\sum | |
| x=1 |
xn-1,n\right)=1.
See main article: Lucas–Carmichael number.
A positive composite integer
n
n
p
399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095, 20705, 20999, 22847, 29315, 31535, 46079, 51359, 60059, 63503, 67199, 73535, 76751, 80189, 81719, 88559, 90287, ...
Quasi–Carmichael numbers are squarefree composite numbers with the property that for every prime factor of, divides positively with being any integer besides 0. If, these are Carmichael numbers, and if, these are Lucas–Carmichael numbers. The first Quasi–Carmichael numbers are:
35, 77, 143, 165, 187, 209, 221, 231, 247, 273, 299, 323, 357, 391, 399, 437, 493, 527, 561, 589, 598, 713, 715, 899, 935, 943, 989, 1015, 1073, 1105, 1147, 1189, 1247, 1271, 1295, 1333, 1517, 1537, 1547, 1591, 1595, 1705, 1729, ...
See main article: Knödel number.
An n-Knödel number for a given positive integer n is a composite number m with the property that each coprime to m satisfies . The case are Carmichael numbers.
Carmichael numbers can be generalized using concepts of abstract algebra.
The above definition states that a composite integer n is Carmichaelprecisely 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.
According to Howe, 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331 is an order 2 Carmichael number. This product is equal to 443,372,888,629,441.[22]
Korselt's criterion can be generalized to higher-order Carmichael numbers, as shown by Howe.
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.
aP-1\equiv1\bmodP
1018
n
pi\midpj-1
pi
pj
n
n
pi