number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...

, a Carmichael number is a

composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Accordingly it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime numb ...

which in

modular arithmetic In mathematics, modular arithmetic is a system of arithmetic operations for integers, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to mo ...

satisfies the

congruence relation In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group (mathematics), group, ring (mathematics), ring, or vector space) that is compatible with the structure in the ...

: :

b^n\equiv b\pmod

for all integers . The relation may also be expressed in the form: :

b^\equiv 1\pmod

for all integers

b

that are

relatively prime In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...

to . They are

infinite Infinite may refer to: Mathematics *Infinite set, a set that is not a finite set *Infinity, an abstract concept describing something without any limit Music Performers *Infinite (group), a South Korean boy band *Infinite (rapper), Canadian ra ...

in number. Robert Daniel Carmichael

They constitute the comparatively rare instances where the strict converse of

Fermat's Little Theorem In number theory, Fermat's little theorem states that if is a prime number, then for any integer , the number is an integer multiple of . In the notation of modular arithmetic, this is expressed as a^p \equiv a \pmod p. For example, if and , t ...

does not hold. This fact precludes the use of that theorem as an absolute test of

primality A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

. The Carmichael numbers form the subset ''K''₁ of the

Knödel number In number theory, an ''n''-Knödel number for a given positive integer ''n'' is a composite number ''m'' with the property that each ''i'' < ''m''

s. The Carmichael numbers were named after the American mathematician

Robert Carmichael Robert Daniel Carmichael (March 1, 1879 – May 2, 1967) was an American mathematician. Biography Carmichael was born in Goodwater, Alabama. He attended Lineville College, briefly, and he earned his bachelor's degree in 1898, while he was s ...

by Nicolaas Beeger, in 1950.

Øystein Ore Øystein Ore (7 October 1899 – 13 August 1968) was a Norwegian mathematician known for his work in ring theory, Galois connections, graph theory, and the history of mathematics. Life Ore graduated from the University of Oslo in 1922, with a ...

had referred to them in 1948 as numbers with the "Fermat property", or "''F'' numbers" for short.

Overview

Fermat's little theorem In number theory, Fermat's little theorem states that if is a prime number, then for any integer , the number is an integer multiple of . In the notation of modular arithmetic, this is expressed as a^p \equiv a \pmod p. For example, if and , t ...

states that if

p

is a

prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...

, then for any

integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

, the number

b^p-b

is an integer multiple of . Carmichael numbers are composite numbers which have the same property. Carmichael numbers are also called

Fermat pseudoprime In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem. Definition Fermat's little theorem states that if p is prime and a is coprime to p, then a^-1 is divisible by p. F ...

s or absolute Fermat pseudoprimes. A Carmichael number will pass a

Fermat primality test The Fermat primality test is a probabilistic test to determine whether a number is a probable prime. Concept Fermat's little theorem states that if ''p'' is prime and ''a'' is not divisible by ''p'', then :a^ \equiv 1 \pmod. If one wants to tes ...

to every base

b

relatively prime to the number, even though it is not actually prime. This makes tests based on Fermat's Little Theorem less effective than strong probable prime tests such as the

Baillie–PSW primality test The Baillie–PSW primality test is a probabilistic or possibly deterministic primality testing algorithm that determines whether a number is composite or is a probable prime. It is named after Robert Baillie, Carl Pomerance, John Selfridge, ...

and the

Miller–Rabin primality test The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen pr ...

. However, no Carmichael number is either an

Euler–Jacobi pseudoprime In number theory, an odd integer ''n'' is called an Euler–Jacobi probable prime (or, more commonly, an Euler probable prime) to base ''a'', if ''a'' and ''n'' are coprime, and :a^ \equiv \left(\frac\right)\pmod where \left(\frac\right) is the ...

or a

strong pseudoprime Strong may refer to: Education * The Strong, an educational institution in Rochester, New York, United States * Strong Hall (Lawrence, Kansas), an administrative hall of the University of Kansas * Strong School, New Haven, Connecticut, United ...

to every base relatively prime to it so, in theory, either an Euler or a strong probable prime test could prove that a Carmichael number is, in fact, composite. Arnault gives a 397-digit Carmichael number

N

that is a ''strong'' pseudoprime to all ''prime'' bases less than 307: :

N =  p \cdot (313(p - 1) + 1) \cdot (353(p - 1) + 1 )

where :

p =

29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883
is a 131-digit prime.

p

is the smallest prime factor of , so this Carmichael number is also a (not necessarily strong) pseudoprime to all bases less than . As numbers become larger, Carmichael numbers become increasingly rare. For example, there are 20,138,200 Carmichael numbers between 1 and 10²¹ (approximately one in 50 trillion (5·10¹³) numbers).

Korselt's criterion

An alternative and equivalent definition of Carmichael numbers is given by Korselt's criterion. : Theorem ( A. Korselt 1899): A positive composite integer

n

is a Carmichael number if and only if

n

square-free {{no footnotes, date=December 2015 In mathematics, a square-free element is an element ''r'' of a unique factorization domain ''R'' that is not divisible by a non-trivial square. This means that every ''s'' such that s^2\mid r is a unit of ''R''. ...

, and for all

prime divisor A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

p

of , it is true that . It follows from this theorem that all Carmichael numbers are odd, since any

even Even may refer to: General * Even (given name), a Norwegian male personal name * Even (surname), a Breton surname * Even (people), an ethnic group from Siberia and Russian Far East **Even language, a language spoken by the Evens * Odd and Even, a ...

composite number that is square-free (and hence has only one prime factor of two) will have at least one odd prime factor, and thus

p-1  \mid n-1

results in an even dividing an odd, a contradiction. (The oddness of Carmichael numbers also follows from the fact that

-1

is a Fermat witness for any even composite number.) From the criterion it also follows that Carmichael numbers are

cyclic Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in s ...

. Additionally, it follows that there are no Carmichael numbers with exactly two prime divisors.

Discovery

The first seven Carmichael numbers, from 561 to 8911, were all found by the Czech mathematician

Václav Šimerka Václav Šimerka (20 December 1819 – 26 December 1887) was a Czech mathematician, priest, physicist and philosopher. He wrote the first Czech text on calculus and is credited for discovering the first seven Carmichael numbers in 1885. Biograp ...

in 1885 (thus preceding not just Carmichael but also Korselt, although Šimerka did not find anything like Korselt's criterion). His work, published in Czech scientific journal '' Časopis pro pěstování matematiky a fysiky'', however, remained unnoticed. Vaclav Simerka

Korselt was the first who observed the basic properties of Carmichael numbers, but he did not give any examples. That 561 is a Carmichael number can be seen with Korselt's criterion. Indeed,

561 = 3 \cdot 11 \cdot 17

is square-free and ,

10 \mid 560

and . The next six Carmichael numbers are : :

1105 = 5 \cdot 13 \cdot 17 \qquad (4 \mid 1104;\quad 12 \mid 1104;\quad 16 \mid 1104)

1729 = 7 \cdot 13 \cdot 19 \qquad (6 \mid 1728;\quad 12 \mid 1728;\quad 18 \mid 1728)

2465 = 5 \cdot 17 \cdot 29 \qquad (4 \mid 2464;\quad 16 \mid 2464;\quad 28 \mid 2464)

2821 = 7 \cdot 13 \cdot 31 \qquad (6 \mid 2820;\quad 12 \mid 2820;\quad 30 \mid 2820)

6601 = 7 \cdot 23 \cdot 41 \qquad (6 \mid 6600;\quad 22 \mid 6600;\quad 40 \mid 6600)

8911 = 7 \cdot 19 \cdot 67 \qquad (6 \mid 8910;\quad 18 \mid 8910;\quad 66 \mid 8910).

In 1910, Carmichael himself also published the smallest such number, 561, and the numbers were later named after him. Jack Chernick proved a theorem in 1939 which can be used to construct a

subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...

of Carmichael numbers. The number

(6k + 1)(12k + 1)(18k + 1)

is a Carmichael number if its three factors are all prime. Whether this formula produces an infinite quantity of Carmichael numbers is an open question (though it is implied by

Dickson's conjecture In number theory, a branch of mathematics, Dickson's conjecture is the conjecture stated by that for a finite set of linear forms , , ..., with , there are infinitely many positive integers for which they are all prime, unless there is a congru ...

Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...

heuristically argued there should be infinitely many Carmichael numbers. In 1994 W. R. (Red) Alford,

Andrew Granville Andrew James Granville (born 7 September 1962) is a British mathematician, working in the field of number theory. Education Granville received his Bachelor of Arts (Honours) (1983) and his Certificate of Advanced Studies (Distinction) (1984) ...

and

Carl Pomerance Carl Bernard Pomerance (born 1944 in Joplin, Missouri) is an American number theorist. He attended college at Brown University and later received his Ph.D. from Harvard University in 1972 with a dissertation proving that any odd perfect number ...

used a bound on Olson's constant to show that there really do exist infinitely many Carmichael numbers. Specifically, they showed that for sufficiently large

n

, there are at least

n^

Carmichael numbers between 1 and . Thomas Wright proved that if

a

and

m

are relatively prime, then there are infinitely many Carmichael numbers in the

arithmetic progression An arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference from any succeeding term to its preceding term remains constant throughout the sequence. The constant difference is called common difference of that ...

, where . Löh and Niebuhr in 1992 found some very large Carmichael numbers, including one with 1,101,518 factors and over 16 million digits. This has been improved to 10,333,229,505 prime factors and 295,486,761,787 digits, so the largest known Carmichael number is much greater than the

largest known prime The largest known prime number is , a number which has 41,024,320 digits when written in the decimal system. It was found on October 12, 2024, on a cloud-based virtual machine volunteered by Luke Durant, a 36-year-old researcher from San Jose, Cali ...

Properties

Factorizations

Carmichael numbers have at least three positive prime factors. The first Carmichael numbers with

k = 3, 4, 5, \ldots

prime factors are : The first Carmichael numbers with 4 prime factors are : 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 1729 is the natural number following 1728 (number), 1728 and preceding 1730. It is the first nontrivial taxicab number, expressed as the Sum of two cubes, sum of two cubic positive integers in two different ways. It is known as the Ramanujan numbe ...

: the smallest number that can be expressed as the

sum of two cubes In mathematics, the sum of two cubes is a cubed number added to another cubed number. Factorization Every sum of cubes may be factored according to the identity a^3 + b^3 = (a + b)(a^2 - ab + b^2) in elementary algebra. Binomial numbers g ...

(of positive numbers) in two different ways.

Distribution

Let

C(X)

denote the number of Carmichael numbers less than or equal to . The distribution of Carmichael numbers by powers of 10 : In 1953,

Knödel Knödel (; and ) or Klöße (; : ''Kloß'') are Boiling, boiled dumplings commonly found in Central European cuisine, Central European and East European cuisine. Countries in which their variant of is popular include Austria, Bosnia, Croatia, ...

proved the

upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of . Dually, a lower bound or minorant of is defined to be an element of that is less ...

: :

C(X) < X \exp\left(\right)

for some constant . In 1956, Erdős improved the bound to :

C(X) < X \exp\left(\frac\right)

for some constant . He further gave a

heuristic argument A heuristic argument is an argument that reasons from the value of a method or principle that has been shown experimentally (especially through trial-and-error) to be useful or convincing in learning, discovery and problem-solving, but whose line ...

suggesting that this upper bound should be close to the true growth rate of . In the other direction, Alford, Granville and Pomerance proved in 1994 that for

sufficiently large In the mathematical areas of number theory and analysis, an infinite sequence or a function is said to eventually have a certain property, if it does not have the said property across all its ordered instances, but will after some instances have ...

''X'', :

C(X) > X^\frac.

In 2005, this bound was further improved by Harman to :

C(X) > X^

who subsequently improved the exponent to . Regarding the asymptotic distribution of Carmichael numbers, there have been several conjectures. In 1956, Erdős conjectured that there were

X^

Carmichael numbers for ''X'' sufficiently large. In 1981, Pomerance sharpened Erdős' heuristic arguments to conjecture that there are at least :

X \cdot L(X)^

Carmichael numbers up to , where . However, inside current computational ranges (such as the count of Carmichael numbers performed by Goutier up to 10²²), these conjectures are not yet borne out by the data; empirically, the exponent is

C(X) \approx X^

for the highest available count (C(X)=49679870 for X= 10²²). In 2021, Daniel Larsen proved an analogue of

Bertrand's postulate In number theory, Bertrand's postulate is the theorem that for any integer n > 3, there exists at least one prime number p with :n < p < 2n - 2. A less restrictive formulation is: for every

n > 1

, there is always at least one ...

for Carmichael numbers first conjectured by Alford, Granville, and Pomerance in 1994. Using techniques developed by

Yitang Zhang Yitang Zhang (; born February 5, 1955) is a Chinese-American mathematician primarily working on number theory and a professor of mathematics at the University of California, Santa Barbara since 2015. Previously working at the University of New ...

and James Maynard to establish results concerning small gaps between primes, his work yielded the much stronger statement that, for any

\delta>0

and sufficiently large

x

in terms of

\delta

, there will always be at least :

\exp

Carmichael numbers between

x

and :

x+\frac.

Generalizations

The notion of Carmichael number generalizes to a Carmichael ideal in any

number field In mathematics, an algebraic number field (or simply number field) is an extension field K of the field of rational numbers such that the field extension K / \mathbb has finite degree (and hence is an algebraic field extension). Thus K is a ...

. For any nonzero

prime ideal In algebra, a prime ideal is a subset of a ring (mathematics), ring that shares many important properties of a prime number in the ring of Integer#Algebraic properties, integers. The prime ideals for the integers are the sets that contain all th ...

\mathfrak p

in , we have

\alpha^ \equiv \alpha \bmod

for all

\alpha

in , where

(\mathfrak p)

is the norm of the

ideal Ideal may refer to: Philosophy * Ideal (ethics), values that one actively pursues as goals * Platonic ideal, a philosophical idea of trueness of form, associated with Plato Mathematics * Ideal (ring theory), special subsets of a ring considered ...

. (This generalizes Fermat's little theorem, that

m^p \equiv m \bmod p

for all integers when is prime.) Call a nonzero ideal

\mathfrak a

_K

Carmichael if it is not a prime ideal and

\alpha^ \equiv \alpha \bmod

for all , where

(\mathfrak a)

is the norm of the ideal . When is , the ideal

\mathfrak a

principal Principal may refer to: Title or rank * Principal (academia), the chief executive of a university ** Principal (education), the head of a school * Principal (civil service) or principal officer, the senior management level in the UK Civil Ser ...

, and if we let be its positive generator then the ideal

\mathfrak a = (a)

is Carmichael exactly when is a Carmichael number in the usual sense. When is larger than the

rational Rationality is the quality of being guided by or based on reason. In this regard, a person acts rationally if they have a good reason for what they do, or a belief is rational if it is based on strong evidence. This quality can apply to an ...

s it is easy to write down Carmichael ideals in : for any prime number that splits completely in , the principal ideal

p_K

is a Carmichael ideal. Since infinitely many prime numbers split completely in any number field, there are infinitely many Carmichael ideals in . For example, if is any prime number that is 1 mod 4, the ideal in the

Gaussian integer In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as \mathbf ...

\mathbb Z /math> is a Carmichael ideal.

Both prime and Carmichael numbers satisfy the following equality:
: \gcd \left(\sum_^ x^, n\right) = 1.

Lucas–Carmichael number

A positive composite integer

n

is a Lucas–Carmichael number if and only if

n

, and for all

p

of , it is true that . The first Lucas–Carmichael numbers are: : 399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095, 20705, 20999, 22847, 29315, 31535, 46079, 51359, 60059, 63503, 67199, 73535, 76751, 80189, 81719, 88559, 90287, ...

Quasi–Carmichael number

Quasi–Carmichael numbers are squarefree composite numbers with the property that for every prime factor of , divides positively with being any integer besides 0. If , these are Carmichael numbers, and if , these are Lucas–Carmichael numbers. The first Quasi–Carmichael numbers are: : 35, 77, 143, 165, 187, 209, 221, 231, 247, 273, 299, 323, 357, 391, 399, 437, 493, 527, 561, 589, 598, 713, 715, 899, 935, 943, 989, 1015, 1073, 1105, 1147, 1189, 1247, 1271, 1295, 1333, 1517, 1537, 1547, 1591, 1595, 1705, 1729, ...

Knödel number

An ''n''-Knödel number for a given

positive integer In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...

''n'' is a

''m'' with the property that each

coprime In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...

to ''m'' satisfies . The case are Carmichael numbers.

Higher-order Carmichael numbers

Carmichael numbers can be generalized using concepts of

abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures, which are set (mathematics), sets with specific operation (mathematics), operations acting on their elements. Algebraic structur ...

. The above definition states that a composite integer ''n'' is Carmichael precisely when the ''n''th-power-raising function ''p''_''n'' from the

ring (The) Ring(s) may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell Arts, entertainment, and media Film and TV * ''The Ring'' (franchise), a ...

Z_''n'' of integers modulo ''n'' to itself is the identity function. The identity is the only Z_''n''-

algebra Algebra is a branch of mathematics that deals with abstract systems, known as algebraic structures, and the manipulation of expressions within those systems. It is a generalization of arithmetic that introduces variables and algebraic ope ...

endomorphism In mathematics, an endomorphism is a morphism from a mathematical object to itself. An endomorphism that is also an isomorphism is an automorphism. For example, an endomorphism of a vector space is a linear map , and an endomorphism of a g ...

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 ''n''th-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.

An order-2 Carmichael number

According to Howe, 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331 is an order 2 Carmichael number. This product is equal to 443,372,888,629,441.

Properties

Korselt's criterion can be generalized to higher-order Carmichael numbers, as shown by Howe. 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.

Notes

References

* * * * * * *

External links

*
Encyclopedia of Mathematics

Table of Carmichael numbers

Tables of Carmichael numbers with many prime factors

* *

{{Classes of natural numbers Eponymous numbers in mathematics Integer sequences Modular arithmetic Pseudoprimes