Vfrdtyky

In number theory, a Carmichael number is a composite number n{displaystyle n} which satisfies the modular arithmetic congruence relation:

bn−1≡1(modn){displaystyle b^{n-1}equiv 1{pmod {n}}}

for all integers b{displaystyle b} which are relatively prime to n{displaystyle n}.
^[1]
They are named for Robert Carmichael.
The Carmichael numbers are the subset K₁ of the Knödel numbers.

Equivalently, a Carmichael number is a composite number n{displaystyle n} for which

bn≡b(modn){displaystyle b^{n}equiv b{pmod {n}}}

for all integers b{displaystyle b}.
^[2]

Overview

Fermat's little theorem states that if p is a prime number, then for any integer b, the number b ^p − b is an integer multiple of p. Carmichael numbers are composite numbers which have this 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
^[3]
so, in theory, either an Euler or a strong probable prime test could prove that a Carmichael number is, in fact, composite.

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).^[4]

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{displaystyle n} is a Carmichael number if and only if n{displaystyle n} is square-free, and for all prime divisors p{displaystyle p} of n{displaystyle n}, it is true that p−1∣n−1{displaystyle p-1mid n-1}.

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∣n−1{displaystyle p-1mid n-1} results in an even dividing an odd, a contradiction. (The oddness of Carmichael numbers also follows from the fact that −1{displaystyle -1} is a Fermat witness for any even composite number.)
From the criterion it also follows that Carmichael numbers are cyclic.^[5][6] Additionally, it follows that there are no Carmichael numbers with exactly two prime factors.

Discovery

Korselt was the first who observed the basic properties of Carmichael numbers, but he did not give any examples. In 1910, Carmichael^[7] found the first and smallest such number, 561, which explains the name "Carmichael number".

That 561 is a Carmichael number can be seen with Korselt's criterion. Indeed, 561=3⋅11⋅17{displaystyle 561=3cdot 11cdot 17} is square-free and 2∣560{displaystyle 2mid 560}, 10∣560{displaystyle 10mid 560} and 16∣560{displaystyle 16mid 560}.

The next six Carmichael numbers are (sequence A002997 in the OEIS):

1105=5⋅13⋅17(4∣1104;12∣1104;16∣1104){displaystyle 1105=5cdot 13cdot 17qquad (4mid 1104;quad 12mid 1104;quad 16mid 1104)}

1729=7⋅13⋅19(6∣1728;12∣1728;18∣1728){displaystyle 1729=7cdot 13cdot 19qquad (6mid 1728;quad 12mid 1728;quad 18mid 1728)}

2465=5⋅17⋅29(4∣2464;16∣2464;28∣2464){displaystyle 2465=5cdot 17cdot 29qquad (4mid 2464;quad 16mid 2464;quad 28mid 2464)}

2821=7⋅13⋅31(6∣2820;12∣2820;30∣2820){displaystyle 2821=7cdot 13cdot 31qquad (6mid 2820;quad 12mid 2820;quad 30mid 2820)}

6601=7⋅23⋅41(6∣6600;22∣6600;40∣6600){displaystyle 6601=7cdot 23cdot 41qquad (6mid 6600;quad 22mid 6600;quad 40mid 6600)}

8911=7⋅19⋅67(6∣8910;18∣8910;66∣8910).{displaystyle 8911=7cdot 19cdot 67qquad (6mid 8910;quad 18mid 8910;quad 66mid 8910).}

These first seven Carmichael numbers, from 561 to 8911, were all found by the Czech mathematician Václav Šimerka in 1885^[8] (thus preceding not just Carmichael but also Korselt, although Šimerka did not find anything like Korselt's criterion).^[9] His work, however, remained unnoticed.

J. Chernick^[10] proved a theorem in 1939 which can be used to construct a subset of Carmichael numbers. The number (6k+1)(12k+1)(18k+1){displaystyle (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{displaystyle n}, there are at least n2/7{displaystyle n^{2/7}} Carmichael numbers between 1 and n{displaystyle n}.^[11]

Löh and Niebuhr in 1992 found some very large Carmichael numbers, including one with 1,101,518 factors and over 16 million digits.

Properties

Factorizations

Carmichael numbers have at least three positive prime factors. For some fixed R, there are infinitely many Carmichael numbers with exactly R factors; in fact, there are infinitely many such R.^[12]

The first Carmichael numbers with k=3,4,5,…{displaystyle k=3,4,5,ldots } prime factors are (sequence A006931 in the OEIS):

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

The first Carmichael numbers with 4 prime factors are (sequence A074379 in the OEIS):

i
1	41041=7⋅11⋅13⋅41{displaystyle 41041=7cdot 11cdot 13cdot 41,}
2	62745=3⋅5⋅47⋅89{displaystyle 62745=3cdot 5cdot 47cdot 89,}
3	63973=7⋅13⋅19⋅37{displaystyle 63973=7cdot 13cdot 19cdot 37,}
4	75361=11⋅13⋅17⋅31{displaystyle 75361=11cdot 13cdot 17cdot 31,}
5	101101=7⋅11⋅13⋅101{displaystyle 101101=7cdot 11cdot 13cdot 101,}
6	126217=7⋅13⋅19⋅73{displaystyle 126217=7cdot 13cdot 19cdot 73,}
7	172081=7⋅13⋅31⋅61{displaystyle 172081=7cdot 13cdot 31cdot 61,}
8	188461=7⋅13⋅19⋅109{displaystyle 188461=7cdot 13cdot 19cdot 109,}
9	278545=5⋅17⋅29⋅113{displaystyle 278545=5cdot 17cdot 29cdot 113,}
10	340561=13⋅17⋅23⋅67{displaystyle 340561=13cdot 17cdot 23cdot 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){displaystyle C(X)} denote the number of Carmichael numbers less than or equal to X{displaystyle X}. The distribution of Carmichael numbers by powers of 10 (sequence A055553 in the OEIS):^[4]

n{displaystyle n}	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
C(10n){displaystyle 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)<Xexp⁡(−k1(log⁡Xlog⁡log⁡X)12){displaystyle C(X)<Xexp left({-k_{1}left(log Xlog log Xright)^{frac {1}{2}}}right)}

for some constant k1{displaystyle k_{1}}.

In 1956, Erdős improved the bound to^[13]

C(X)<Xexp⁡(−k2log⁡Xlog⁡log⁡log⁡Xlog⁡log⁡X){displaystyle C(X)<Xexp left({frac {-k_{2}log Xlog log log X}{log log X}}right)}

for some constant k2{displaystyle k_{2}}. He further gave a heuristic argument suggesting that this upper bound should be close to the true growth rate of C(X){displaystyle C(X)}. The table below gives approximate minimal values for the constant k in the Erdős bound for X=10n{displaystyle X=10^{n}} as n grows:

n{displaystyle n}	4	6	8	10	12	14	16	18	20	21
k	2.19547	1.97946	1.90495	1.86870	1.86377	1.86293	1.86406	1.86522	1.86598	1.86619

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

C(X)>X27.{displaystyle C(X)>X^{frac {2}{7}}.}

In 2005, this bound was further improved by Harman^[14] to

C(X)>X0.332{displaystyle C(X)>X^{0.332}}

who subsequently improved the exponent to 0.7039⋅0.4736=0.33336704>1/3{displaystyle 0.7039cdot 0.4736=0.33336704>1/3}.
^[15]

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

X1−{1+o(1)}log⁡log⁡log⁡Xlog⁡log⁡X{displaystyle X^{1-{frac {{1+o(1)}log log log X}{log log X}}}}

Carmichael numbers up to X. However, inside current computational ranges (such as the counts of Carmichael numbers performed by Pinch^[4] up to 10²¹), these conjectures are not yet borne out by the data.

Generalizations

The notion of Carmichael number generalizes to a Carmichael ideal in any number field K. For any nonzero prime ideal p{displaystyle {mathfrak {p}}} in OK{displaystyle {mathcal {O}}_{K}}, we have αN(p)≡αmodp{displaystyle alpha ^{{rm {N}}({mathfrak {p}})}equiv alpha {bmod {mathfrak {p}}}} for all α{displaystyle alpha } in OK{displaystyle {mathcal {O}}_{K}}, where N(p){displaystyle {rm {N}}({mathfrak {p}})} is the norm of the ideal p{displaystyle {mathfrak {p}}}. (This generalizes Fermat's little theorem, that mp≡mmodp{displaystyle m^{p}equiv m{bmod {p}}} for all integers m when p is prime.) Call a nonzero ideal a{displaystyle {mathfrak {a}}} in OK{displaystyle {mathcal {O}}_{K}} Carmichael if it is not a prime ideal and αN(a)≡αmoda{displaystyle alpha ^{{rm {N}}({mathfrak {a}})}equiv alpha {bmod {mathfrak {a}}}} for all α∈OK{displaystyle alpha in {mathcal {O}}_{K}}, where N(a){displaystyle {rm {N}}({mathfrak {a}})} is the norm of the ideal a{displaystyle {mathfrak {a}}}. When K is Q{displaystyle mathbf {Q} }, the ideal a{displaystyle {mathfrak {a}}} is principal, and if we let a be its positive generator then the ideal a=(a){displaystyle {mathfrak {a}}=(a)} is Carmichael exactly when a is a Carmichael number in the usual sense.

When K is larger than the rationals it is easy to write down Carmichael ideals in OK{displaystyle {mathcal {O}}_{K}}: for any prime number p that splits completely in K, the principal ideal pOK{displaystyle p{mathcal {O}}_{K}} is a Carmichael ideal. Since infinitely many prime numbers split completely in any number field, there are infinitely many Carmichael ideals in OK{displaystyle {mathcal {O}}_{K}}. For example, if p is any prime number that is 1 mod 4, the ideal (p) in the Gaussian integers Z[i] is a Carmichael ideal.

Both prime and Carmichael numbers satisfy the following equality:

gcd(∑x=1n−1xn−1,n)=1{displaystyle gcd left(sum _{x=1}^{n-1}x^{n-1},nright)=1}

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.^[17]

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.

Notes

References

• 
  Carmichael, R. D. (1910). "Note on a new number theory function". Bulletin of the American Mathematical Society. 16 (5): 232–238. doi:10.1090/s0002-9904-1910-01892-9.
  


• 
  Carmichael, R. D. (1912). "On composite numbers P which satisfy the Fermat congruence aP−1≡1modP{displaystyle a^{P-1}equiv 1{bmod {P}}}". American Mathematical Monthly. 19 (2): 22–27. doi:10.2307/2972687.
  


• 
  Chernick, J. (1939). "On Fermat's simple theorem" (PDF). Bull. Amer. Math. Soc. 45: 269–274. doi:10.1090/S0002-9904-1939-06953-X.
  


• 
  Korselt, A. R. (1899). "Problème chinois". L'Intermédiaire des Mathématiciens. 6: 142–143.
  


• 
  Löh, G.; Niebuhr, W. (1996). "A new algorithm for constructing large Carmichael numbers" (PDF). Math. Comp. 65: 823–836. doi:10.1090/S0025-5718-96-00692-8.
  


• 
  Ribenboim, P. (1989). The Book of Prime Number Records. Springer. ISBN 978-0-387-97042-4.
  


• 
  Šimerka, V. (1885). "Zbytky z arithmetické posloupnosti (On the remainders of an arithmetic progression)". Časopis pro pěstování matematiky a fysiky. 14 (5): 221–225.
  

External links

• 
  Hazewinkel, Michiel, ed. (2001) [1994], "Carmichael number", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
  


• Table of Carmichael numbers


• Tables of Carmichael numbers below 1018{displaystyle 10^{18}}
  


• 
  "The Dullness of 1729". MathPages.com.
  


• Weisstein, Eric W. "Carmichael Number". MathWorld.


• Final Answers Modular Arithmetic