Carmichael number

From Wikipedia, the free encyclopedia

In number theory, a Carmichael number is a composite positive integer n which satisfies the congruence b^n − 1 ≡ 1 (mod n) for all integers b which are relatively prime to n (see modular arithmetic). They are named for Robert Carmichael.

1 Overview
- 1.1 Properties
- 1.2 Distribution
2 Higher-order Carmichael numbers
- 2.1 Properties
3 Layman's overview
4 References
5 External links

[edit] Overview

Fermat's little theorem states that all prime numbers have that 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, thus they are always fermat liars. Since Carmichael numbers exist, this primality test cannot be relied upon to prove the primality of a number, although it can still be used to prove a number is composite.

Still, as numbers become larger, Carmichael numbers become very rare. For example, there are 1,401,644 Carmichael numbers between 1 and 10¹⁸ (approximately one in 700 billion numbers.)^[1] This makes tests based on Fermat's Little Theorem slightly risky compared to others such as the Solovay-Strassen primality test.

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

Theorem (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 n, it is true that p − 1 divides n − 1.

It follows from this theorem that all Carmichael numbers are 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 notation a | b means: a divides b).

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

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)

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

Paul Erdős heuristically argued there should be infinitely many Carmichael numbers. In 1994 it was shown by W. R. (Red) Alford, Andrew Granville and Carl Pomerance that there really 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 n.^[2]

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

[edit] Properties

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

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 (sequence A074379 in OEIS):

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

Incidentally, the first Carmichael number (561) is expressible as the sum of two nonnegative first powers in more ways than any smaller number (although admittedly all nonnegative integers share this property). 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 in two different ways.

[edit] Distribution

Let C(X) denote the number of Carmichael numbers less than or equal to X. Erdős proved in his 1956 paper that

C (X) < X .exp( - k log X logloglog X / loglog X)

for some constant k; in the other direction, Alford, Granville and Pomerance proved in their 1994 paper that

C (X) > X 2 / 7

for sufficiently large X and Glyn Harman proved that

C (X) > X 0.332,

again for sufficiently large X ^[3]. Erdős also gave a heuristic suggesting that his upper bound should be close to the true rate of growth of C(X).

The distribution of Carmichael numbers by powers of 10, from Pinch (2006).

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

[edit] 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.

[edit] Properties

Korselt's criterion can be generalized to higher-order Carmichael numbers, as shown by Howe.^[4]

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.

[edit] Layman's overview

To see if a number n is a Carmichael number:

n must not be prime (must have factors)
For every number b less than n which has no factors in common with n
- (b^n − 1) mod n = 1

The following algorithm (in BASIC) performs this test:

INPUT n
n1 = n - 1
fail = 0
somefactor = 0
FOR b = 2 TO n1
 IF coprime(b, n) THEN
  bi = 1
  FOR i = 1 TO n1
   bi = bi * b
   bi = bi MOD n
  NEXT i
  IF bi <> 1 THEN
   fail = b
   EXIT FOR
  END IF
 ELSE
  somefactor = 1
 END IF
NEXT b
IF fail > 0 THEN
 PRINT n; "fails for b="; fail
ELSEIF n <= 1 THEN
 PRINT n; "is 0 or 1"
ELSEIF somefactor = 0 THEN
 PRINT n; "is a prime"
ELSE
 PRINT n; "is a Carmichael number"
END IF

This produces results such as:

560 fails for b= 3 
561 is a Carmichael number
562 fails for b= 3 
563 is a prime
564 fails for b= 5

[edit] References

^ Richard Pinch, "The Carmichael numbers up to 10¹⁸", April 2006 (building on his earlier work [1][2][3]).
^ W. R. Alford, A. Granville, and C. Pomerance. "There are Infinitely Many Carmichael Numbers." Annals of Mathematics 139 (1994) 703-722.
^ Glyn Harman. "On the number of Carmichael numbers up to X." Bull. Lond. Math. Soc. 37 (2005) 641-650.
^ Everett W. Howe. "Higher-order Carmichael numbers." Mathematics of Computation 69 (2000), pp. 1711–1719.

Chernick, J. (1935). On Fermat's simple theorem. Bull. Amer. Math. Soc. 45, 269–274.
Ribenboim, Paolo (1996). The New Book of Prime Number Records.
Löh, Günter and Niebuhr, Wolfgang (1996). A new algorithm for constructing large Carmichael numbers(pdf)
Korselt (1899). Probleme chinois. L'intermediaire des mathematiciens, 6, 142–143.
Carmichael, R. D. (1912) On composite numbers P which satisfy the Fermat congruence $a^{P-1}\equiv 1\bmod P$ . Am. Math. Month. 19 22–27.
Erdős, Paul (1956). On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4, 201 –206.