Carmichael number

From Academic Kids

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

Contents

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. If Carmichael numbers did not exist, this primality test could always be used to prove compositeness of a number.

Even though, as numbers become larger, Carmichael numbers become rarer, the sheer number of them makes the Fermat primality test largely useless compared to other primality tests such as the Solovay-Strassen primality test. For example, there are 105,212 Carmichael numbers between 1 and 1015.

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

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 Template: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 William Alford, Andrew Granville and Carl Pomerance that there really exist infinitely many Carmichael numbers.

It has also been shown that for sufficiently large n, there are at least n2/7 Carmichael numbers between 1 and n.

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.

Properties

Carmichael numbers have at least three positive prime factors. The first Carmichael numbers with k = 3, 4, 5, … prime factors are (sequence A006931 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=006931) 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 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=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 first powers in more ways than any smaller number (although admittedly all numbers 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.

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.

References

  • 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.
  • Howe, Everett W. (2000). Higher-order Carmichael numbers. Mathematics of Computation 69, 1711–1719. (online version) (http://arxiv.org/abs/math.NT/9812089)
  • Löh, Günter and Niebuhr, Wolgang (1996). A new algorithm for constructing large Carmichael numbers (http://www.ams.org/mcom/1996-65-214/S0025-5718-96-00692-8/S0025-5718-96-00692-8.pdf)(pdf)

External link

es:Número de Carmichael fr:Nombre de Carmichaël sl:Carmichaelovo število

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools