Encyclopedia > Carmichael number

  Article Content

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, aN-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 Higher-order Carmichael numbers
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 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.

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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Meselson-Stahl experiment

... was an experiment to prove that DNA replication was semiconservative. Semiconservative replication means that when the double stranded DNA helix was replicated, ...