Carmichael number

A positive integer N is called a Carmichael number if and only if N is composite (i.e. not prime) and for all integers a which are relatively prime to N, a^N-1 is congruent to 1 modulo N (see modular arithmetic). Fermat's little theorem says that all prime numbers have this latter property. In this sense, Carmichael numbers are similar to prime numbers. They are called pseudoprimes.

An alternative and equivalent definition of Carmichael numbers is given by Korselt's theorem from 1899, which says that a positive integer N is a Carmichael number if and only if N is square-free and non-prime, and for all prime divisors p of N, p-1 divides N-1, written as p-1 | N-1. This shows that Carmichael numbers are always odd.

Carmichael numbers are sometimes called also absolute pseudoprimes.

The first known Carmichael number is 561. (Indeed, 561 = 3 · 11 · 17 is squarefree and 2 | 560, 10 | 560 and 16 | 560.) The next Carmichael numbers are (SIDN A002997) (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=002997):

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),

...

Korselt was the first who observed the properties of these numbers but he could not get an example. In 1910 Carmichael[?] gave the example of 561 and hence the name. 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 1 Properties 1 Higher-order Carmichael numbers 1.1 Properties 2 External links

Properties

Carmichael numbers have at least three positive prime factors. The first Carmichael numbers with k= 3, 4, 5, ... prime factors are (SIDN A006931) (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=006931):

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

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.

Properties

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.

External links

• Everett W. Howe, Higher-order Carmichael numbers Math. Comp. 69 (2000) p. 1711-1719, http://arxiv.org/abs/math.NT/9812089