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. Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study. ... A composite number is a positive integer which has a positive divisor other than one or itself. ... The integers are commonly denoted by the above symbol. ... As an abstract term, congruence means similarity between objects. ... In mathematics, the integers a and b are said to be coprime or relatively prime if and only if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1. ... Modular arithmetic (sometimes called modulo arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... Robert Daniel Carmichael (1879-1967) was a leading American mathematician. ...

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. Fermats little theorem (not to be confused with Fermats last theorem) states that if p is a prime number, then for any integer a, This means that if you start with a number, initialized to 1, and repeatedly multiply, for a total of p multiplications, that number by... In mathematics, a prime number, or prime for short, is a natural number greater than one and whose only distinct positive divisors are 1 and itself. ... A pseudoprime is a probable prime (an integer which shares a property common to all prime numbers) which is not actually prime. ...

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. The Fermat primality test is a probabilistic test to determine if a number is composite or probably prime. ...

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. The Solovay-Strassen primality test, developed by Robert M. Solovay and Volker Strassen, is a probabilistic test to determine if a number is composite or probably prime. ...

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. In mathematics, a square-free, or quadratfrei, integer is one divisible by no perfect square, except 1. ...

It follows from this theorem that all Carmichael numbers are odd. In mathematics, any integer (whole number) is either even or 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. Robert Daniel Carmichael (1879-1967) was a leading American mathematician. ... 561 is the natural number following 560 and followed by 562. ...

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). In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ...

The next few Carmichael numbers are (sequence A002997 in OEIS): The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

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. 1729 Cardinal One thousand seven hundred [and] twenty-nine Ordinal 1729th Factorization Divisors 7, 13, 19, 91, 133, 247 Roman numeral MDCCXXIX Binary 11011000001 Octal 3301 Duodecimal 1001 Hexadecimal 6C1 1729 is known as the Hardy-Ramanujan number, after a famous anecdote of the British mathematician G. H. Hardy regarding... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ...

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] Paul ErdÅ‘s also Pál ErdÅ‘s, in English Paul Erdos or Paul Erdös, (March 26, 1913 – September 20, 1996) was an immensely prolific (and famously eccentric) Hungarian mathematician who, with hundreds of collaborators, worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set... W. R. (Red) Alford was an American mathematician who worked in the field of number theory. ... Andrew Granville is a British mathematician, working in the field of number theory. ... One of the top number theorists of our time, Carl Pomerance received his PhD from Harvard University in 1972 and immediately joined the faculty at the University of Georgia, becoming full professor in 1982. ...

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. 1992 (MCMXCII) was a leap year starting on Wednesday. ...

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): The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

The first Carmichael numbers with 4 prime factors are (sequence A074379 in OEIS): The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

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. 561 is the natural number following 560 and followed by 562. ... 1729 Cardinal One thousand seven hundred [and] twenty-nine Ordinal 1729th Factorization Divisors 7, 13, 19, 91, 133, 247 Roman numeral MDCCXXIX Binary 11011000001 Octal 3301 Duodecimal 1001 Hexadecimal 6C1 1729 is known as the Hardy-Ramanujan number, after a famous anecdote of the British mathematician G. H. Hardy regarding...

Distribution

Let C(X) denote the number of Carmichael numbers less than or equal to X. Erdős proved in his 1956 paper that Paul ErdÅ‘s also Pál ErdÅ‘s, in English Paul Erdos or Paul Erdös, (March 26, 1913 – September 20, 1996) was an immensely prolific (and famously eccentric) Hungarian mathematician who, with hundreds of collaborators, worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set...

C(X) < X.exp( − klogXlogloglogX / loglogX)

for some constant k; in the other direction, Alford, Granville and Pomerance proved in their 1994 paper that William P. Alford is a Henry L. Stimson Professor of Law at Harvard Law School, Vice Dean for the Graduate Program and International Legal Studies, and Director of East Asian Legal Studies. ... Andrew Granville is a British mathematician, working in the field of number theory. ... One of the top number theorists of our time, Carl Pomerance received his PhD from Harvard University in 1972 and immediately joined the faculty at the University of Georgia, becoming full professor in 1982. ...

C(X) > X^{2 / 7}

for sufficiently large X and Glyn Harman proved that Glyn Harman (born 2 November 1956) is a British mathematician. ...

C(X) > X^0.332,

again for sufficiently large X ^[3]. This author has subsequently improved the exponent to just over 1/3. Erdős also gave a heuristic suggesting that his upper bound should be close to the true rate of growth of C(X). Paul ErdÅ‘s also Pál ErdÅ‘s, in English Paul Erdos or Paul Erdös, (March 26, 1913 – September 20, 1996) was an immensely prolific (and famously eccentric) Hungarian mathematician who, with hundreds of collaborators, worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set...

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

Higher-order Carmichael numbers

Carmichael numbers can be generalized using concepts of abstract algebra. Abstract algebra is the field of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras. ...

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. In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have properties listed below. ... In mathematics, an algebra over a field K, or a K-algebra, is a vector space A over K equipped with a compatible notion of multiplication of elements of A. A straightforward generalisation allows K to be any commutative ring. ... In mathematics, an endomorphism is a morphism (or homomorphism) from a mathematical object to itself. ...

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. In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, where instead of requiring the scalars to lie in a field, the scalars may lie in an arbitrary ring. ...

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.

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 

References

1. ^ Richard Pinch, "The Carmichael numbers up to 10¹⁸", April 2006 (building on his earlier work [1][2][3]).
2. ^ W. R. Alford, A. Granville, and C. Pomerance. "There are Infinitely Many Carmichael Numbers." Annals of Mathematics 139 (1994) 703-722.
3. ^ Glyn Harman. "On the number of Carmichael numbers up to X." Bull. Lond. Math. Soc. 37 (2005) 641-650.
4. ^ 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 . Am. Math. Month. 19 22–27.
• Erdős, Paul (1956). On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4, 201 –206.

External links

• Table of Carmichael numbers
• Mathpages: The Dullness of 1729
• Weisstein, Eric W., Carmichael Number at MathWorld.
• Final Answers Modular Arithmetic