Carmichael number

In number theory, a Carmichael number is a composite number Template:Tmath which in modular arithmetic satisfies the congruence relation:

$b^n\equiv b(\mathrm{mod}n)$

for all integers Template:Tmath. The relation may also be expressed in the form:

$b^{n-1}\equiv 1(\mathrm{mod}n)$

for all integers $b$ that are relatively prime to Template:Tmath. They are infinite in number.

Robert Daniel Carmichael

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.

The Carmichael numbers form the subset K₁ 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.

Overview

Fermat's little theorem states that if $p$ is a prime number, then for any integer Template:Tmath, the number $b^p-b$ is an integer multiple of Template:Tmath. Carmichael numbers are composite numbers which have the same property. Carmichael numbers are also called Fermat pseudoprimes or absolute Fermat pseudoprimes. A Carmichael number will pass a Fermat primality test to every base $b$ relatively prime to the number, even though it is not actually prime. This makes tests based on Fermat's Little Theorem less effective than strong probable prime tests such as the Baillie–PSW primality test and the Miller–Rabin primality test.

However, no Carmichael number is either an Euler–Jacobi pseudoprime or a strong pseudoprime to every base relatively prime to it so, in theory, either an Euler or a strong probable prime test could prove that a Carmichael number is, in fact, composite.

Arnault gives a 397-digit Carmichael number $N$ that is a strong pseudoprime to all prime bases less than 307:

$N=p\cdot (313(p-1)+1)\cdot (353(p-1)+1)$

where

$p=$Template:Hsp2Template:Hsp9674495668Template:Hsp6855105501Template:Hsp5417464290Template:Hsp5332730771Template:Hsp9917998530Template:Hsp4335099507Template:Hsp5531276838Template:Hsp7531717701Template:Hsp9959423859Template:Hsp6428121188Template:Hsp0336647542Template:Hsp1834556249Template:Hsp3168782883

is a 131-digit prime. $p$ is the smallest prime factor of Template:Tmath, so this Carmichael number is also a (not necessarily strong) pseudoprime to all bases less than Template:Tmath.

As numbers become larger, Carmichael numbers become increasingly rare. For example, there are 20,138,200 Carmichael numbers between 1 and 10²¹ (approximately one in 50 trillion (5·10¹³) numbers).

Korselt's criterion

An alternative and equivalent definition of Carmichael numbers is given by Korselt's criterion.

Theorem (A. Korselt 1899): A positive composite integer $n$ is a Carmichael number if and only if $n$ is square-free, and for all prime divisors $p$ of Template:Tmath, it is true that Template:Tmath.

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\mid n-1$ results in an even dividing an odd, a contradiction. (The oddness of Carmichael numbers also follows from the fact that $-1$ is a Fermat witness for any even composite number.) From the criterion it also follows that Carmichael numbers are cyclic. Additionally, it follows that there are no Carmichael numbers with exactly two prime divisors.

Discovery

The first seven Carmichael numbers, from 561 to 8911, were all found by the Czech mathematician Václav Šimerka in 1885 (thus preceding not just Carmichael but also Korselt, although Šimerka did not find anything like Korselt's criterion). His work, published in Czech scientific journal Časopis pro pěstování matematiky a fysiky, however, remained unnoticed.

Václav Šimerka listed the first seven Carmichael numbers

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\cdot 11\cdot 17$ is square-free and Template:Tmath, $10\mid 560$ and Template:Tmath. The next six Carmichael numbers are Template:OEIS:

$1105=5\cdot 13\cdot 17(4\mid 1104;12\mid 1104;16\mid 1104)$

$1729=7\cdot 13\cdot 19(6\mid 1728;12\mid 1728;18\mid 1728)$

$2465=5\cdot 17\cdot 29(4\mid 2464;16\mid 2464;28\mid 2464)$

$2821=7\cdot 13\cdot 31(6\mid 2820;12\mid 2820;30\mid 2820)$

$6601=7\cdot 23\cdot 41(6\mid 6600;22\mid 6600;40\mid 6600)$

$8911=7\cdot 19\cdot 67(6\mid 8910;18\mid 8910;66\mid 8910).$

In 1910, Carmichael himself also published the smallest such number, 561, and the numbers were later named after him.

Jack Chernick proved a theorem in 1939 which can be used to construct a subset of Carmichael numbers. The number $(6k+1)(12k+1)(18k+1)$ is a Carmichael number if its three factors are all prime. Whether this formula produces an infinite quantity of Carmichael numbers is an open question (though it is implied by Dickson's conjecture).

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$, there are at least $n^{2/7}$ Carmichael numbers between 1 and Template:Tmath.

Thomas Wright proved that if $a$ and $m$ are relatively prime, then there are infinitely many Carmichael numbers in the arithmetic progression Template:Tmath, where Template:Tmath.

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, so the largest known Carmichael number is much greater than the largest known prime.

Properties

Factorizations

Carmichael numbers have at least three positive prime factors. The first Carmichael numbers with $k=3,4,5,\dots$ prime factors are Template:OEIS:

k
3	$561=3\cdot 11\cdot 17$
4	$41041=7\cdot 11\cdot 13\cdot 41$
5	$825265=5\cdot 7\cdot 17\cdot 19\cdot 73$
6	$321197185=5\cdot 19\cdot 23\cdot 29\cdot 37\cdot 137$
7	$5394826801=7\cdot 13\cdot 17\cdot 23\cdot 31\cdot 67\cdot 73$
8	$232250619601=7\cdot 11\cdot 13\cdot 17\cdot 31\cdot 37\cdot 73\cdot 163$
9	$9746347772161=7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 31\cdot 37\cdot 41\cdot 641$

The first Carmichael numbers with 4 prime factors are Template:OEIS:

i
1	$41041=7\cdot 11\cdot 13\cdot 41$
2	$62745=3\cdot 5\cdot 47\cdot 89$
3	$63973=7\cdot 13\cdot 19\cdot 37$
4	$75361=11\cdot 13\cdot 17\cdot 31$
5	$101101=7\cdot 11\cdot 13\cdot 101$
6	$126217=7\cdot 13\cdot 19\cdot 73$
7	$172081=7\cdot 13\cdot 31\cdot 61$
8	$188461=7\cdot 13\cdot 19\cdot 109$
9	$278545=5\cdot 17\cdot 29\cdot 113$
10	$340561=13\cdot 17\cdot 23\cdot 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.

Distribution

Let $C(X)$ denote the number of Carmichael numbers less than or equal to Template:Tmath. The distribution of Carmichael numbers by powers of 10 Template:OEIS:

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
$C(10^n)$	0	0	1	7	16	43	105	255	646	1547	3605	8241	19279	44706	105212	246683	585355	1401644	3381806	8220777	20138200

In 1953, Knödel proved the upper bound:

$C(X)<X\exp \left(-k_1{(\log X\log \log X)}^{\frac{1}{2}}\right)$

for some constant Template:Tmath.

In 1956, Erdős improved the bound to

$C(X)<X\exp \left(\frac{-k_2\log X\log \log \log X}{\log \log X}\right)$

for some constant Template:Tmath. He further gave a heuristic argument suggesting that this upper bound should be close to the true growth rate of Template:Tmath.

In the other direction, Alford, Granville and Pomerance proved in 1994 that for sufficiently large X,

$C(X)>X^{\frac{2}{7}}.$

In 2005, this bound was further improved by Harman to

$C(X)>X^{0.332}$

who subsequently improved the exponent to Template:Tmath.

Regarding the asymptotic distribution of Carmichael numbers, there have been several conjectures. In 1956, Erdős conjectured that there were $X^{1-o(1)}$ Carmichael numbers for X sufficiently large. In 1981, Pomerance sharpened Erdős' heuristic arguments to conjecture that there are at least

$X\cdot L(X{)}^{-1+o(1)}$

Carmichael numbers up to Template:Tmath, where Template:Tmath.

However, inside current computational ranges (such as the counts of Carmichael numbers performed by Pinch up to 10²¹), 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. 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$ and sufficiently large $x$ in terms of $\delta$, there will always be at least

$\exp \left(\frac{\log x}{(\log \log x{)}^{2+\delta }}\right)$

Carmichael numbers between $x$ and

$x+\frac{x}{(\log x{)}^{\frac{1}{2+\delta }}}.$

Generalizations

The notion of Carmichael number generalizes to a Carmichael ideal in any number field Template:Tmath. For any nonzero prime ideal $𝔭$ in Template:Tmath, we have ${\alpha }^{\mathrm{N}(𝔭)}\equiv \alpha mod𝔭$ for all $\alpha$ in Template:Tmath, where $\mathrm{N}(𝔭)$ is the norm of the ideal Template:Tmath. (This generalizes Fermat's little theorem, that $m^p\equiv mmodp$ for all integers Template:Tmath when Template:Tmath is prime.) Call a nonzero ideal $𝔞$ in ${𝒪}_K$ Carmichael if it is not a prime ideal and ${\alpha }^{\mathrm{N}(𝔞)}\equiv \alpha mod𝔞$ for all Template:Tmath, where $\mathrm{N}(𝔞)$ is the norm of the ideal Template:Tmath. When Template:Tmath is Template:Tmath, the ideal $𝔞$ is principal, and if we let Template:Tmath be its positive generator then the ideal $𝔞=(a)$ is Carmichael exactly when Template:Tmath is a Carmichael number in the usual sense.

When Template:Tmath is larger than the rationals it is easy to write down Carmichael ideals in Template:Tmath: for any prime number Template:Tmath that splits completely in Template:Tmath, the principal ideal $p{𝒪}_K$ is a Carmichael ideal. Since infinitely many prime numbers split completely in any number field, there are infinitely many Carmichael ideals in Template:Tmath. For example, if Template:Tmath is any prime number that is 1 mod 4, the ideal Template:Tmath in the Gaussian integers $\mathbb{Z}[i]$ is a Carmichael ideal.

Both prime and Carmichael numbers satisfy the following equality:

$\gcd (\sum _{x=1}^{n-1}{x}^{n-1},n)=1.$

Lucas–Carmichael number

A positive composite integer $n$ is a Lucas–Carmichael number if and only if $n$ is square-free, and for all prime divisors $p$ of Template:Tmath, it is true that Template:Tmath. The first Lucas–Carmichael numbers are:

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, ... Template:OEIS

Quasi–Carmichael number

Quasi–Carmichael numbers are squarefree composite numbers Template:Tmath with the property that for every prime factor Template:Tmath of Template:Tmath, Template:Tmath divides Template:Tmath positively with Template:Tmath being any integer besides 0. If Template:Tmath, these are Carmichael numbers, and if Template:Tmath, 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, ... Template:OEIS

Knödel number

An n-Knödel number for a given positive integer n is a composite number m with the property that each Template:Tmath coprime to m satisfies Template:Tmath. The Template:Tmath case are Carmichael numbers.

Higher-order Carmichael numbers

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 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 nth-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.

An order-2 Carmichael number

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.

Properties

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.

References

• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Cite journal

External links

• Template:Springer
• Encyclopedia of Mathematics
• Table of Carmichael numbers
• Tables of Carmichael numbers with many prime factors
• Tables of Carmichael numbers below $10^{18}$
• Template:MathPages
• Template:MathWorld
• Final Answers Modular Arithmetic