number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777� ...

, a Carmichael number is a

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

n

, which in

modular arithmetic In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book ...

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, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...

: :

b^n\equiv b\pmod

for all integers

b

. The relation may also be expressed in the form: :

b^\equiv 1\pmod

. for all integers

b

which are

relatively prime In mathematics, 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 equivale ...

n

. Carmichael numbers are named after 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 st ...

, the term having been introduced 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). They are infinite in number. Robert Daniel Carmichael

They constitute the comparatively rare instances where the strict converse of

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

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''

Overview

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

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 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 ...

, then for any

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...

''b'', the number ''b'' − ''b'' is an integer multiple of ''p''. Carmichael numbers are composite numbers which have this 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'p''� ...

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 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 Samuel Wagstaff. The Bailli ...

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 prima ...

. 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 J ...

or a

strong pseudoprime A strong pseudoprime is a composite number that passes the Miller–Rabin primality test. All prime numbers pass this test, but a small fraction of composites also pass, making them "pseudoprimes". Unlike the Fermat pseudoprimes, for which there ex ...

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

N

, so this Carmichael number is also a (not necessarily strong) pseudoprime to all bases less than

p

. 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''. A ...

, 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

n

, it is true that

p - 1 \mid n - 1

. It follows from this theorem that all Carmichael numbers are

odd Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric. Odd may also refer to: Acronym * ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...

, since any even 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 soc ...

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

Discovery

Korselt was the first who observed the basic properties of Carmichael numbers, but he did not give any examples. In 1910, Carmichael found the first and smallest such number, 561, which explains the name "Carmichael number". Vaclav Simerka

That 561 is a Carmichael number can be seen with Korselt's criterion. Indeed,

561 = 3 \cdot 11 \cdot 17

is square-free and

2 \mid 560

10 \mid 560

and

16 \mid 560

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

These 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 Bohemian mathematician, priest, physicist, and philosopher. He wrote the first Czech text on calculus and is credited for discovering the first seven Carmichael numbers, from 561 to ...

in 1885 (thus preceding not just Carmichael but also Korselt, although Šimerka did not find anything like Korselt's criterion). His work, however, remained unnoticed.

J. Chernick ''J. The Jewish News of Northern California'', formerly known as ''Jweekly'', is a weekly print newspaper in Northern California, with its online edition updated daily. It is owned and operated by San Francisco Jewish Community Publications In ...

proved a theorem in 1939 which can be used to construct a

subset In mathematics, 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 are ...

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 congrue ...

Paul Erdős Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 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 ...

heuristically argued there should be infinitely many Carmichael numbers. In 1994 W. R. (Red) Alford, Andrew Granville 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 h ...

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

n.

Thomas Wright proved that if

a

and

m

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

a + k \cdot m

, where

k = 1, 2, \ldots

. 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 24,862,048 digits when written in base 10. It was found via a computer volunteered by Patrick Laroche of the Great Internet Mersenne Prime Search (GIMPS) in 2018. A prime number is a posi ...

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 and preceding 1730. It is a taxicab number, and is variously known as Ramanujan's number and the Ramanujan-Hardy number, after an anecdote of the British mathematician G. H. Hardy when he visited Indian ma ...

: the smallest number that can be expressed as the sum of two cubes (of positive numbers) in two different ways.

Distribution

Let

C(X)

denote the number of Carmichael numbers less than or equal to

X

. The distribution of Carmichael numbers by powers of 10 : In 1953,

Knödel Knödel (; and ) or Klöße (; ) are boiled dumplings commonly found in Central European and East European cuisine. Central European countries in which their variant of ''Knödel'' is popular include Austria, Germany, Hungary, Poland, Romania, ...

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 greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an element ...

: :

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

for some constant

k_1

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

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

for some constant

k_2

. 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

C(X)

. In the other direction, Alford, Granville and Pomerance proved in 1994 that for sufficiently large ''X'', :

C(X) > X^\frac.

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

C(X) > X^

who subsequently improved the exponent to

0.7039 \cdot 0.4736 = 0.33336704 > 1/3

. 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

X

, where

L(x) = \exp

. However, inside current computational ranges (such as the counts of Carmichael numbers performed by Pinch up to 10²¹), these conjectures are not yet borne out by the data. In 2021, Daniel Larsen, a 17-year-old high-school student from

Indiana Indiana () is a U.S. state in the Midwestern United States. It is the 38th-largest by area and the 17th-most populous of the 50 States. Its capital and largest city is Indianapolis. Indiana was admitted to the United States as the 19th s ...

, proved an analogue of

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

n > 1

, there is always ...

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 f ...

''K''. For any nonzero

prime ideal In algebra, a prime ideal is a subset of a ring that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together with ...

\mathfrak p

_K

, we have

\alpha^ \equiv \alpha \bmod

for all

\alpha

_K

, 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 considere ...

\mathfrak p

. (This generalizes Fermat's little theorem, that

m^p \equiv m \bmod p

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

\mathfrak a

_K

Carmichael if it is not a prime ideal and

\alpha^ \equiv \alpha \bmod

for all

\alpha \in _K

, where

(\mathfrak a)

is the norm of the ideal

\mathfrak a

. When ''K'' is

\mathbf Q

, the ideal

\mathfrak a

is principal, and if we let ''a'' be its positive generator then the ideal

\mathfrak a = (a)

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

rational Rationality is the quality of being guided by or based on reasons. 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 abili ...

s it is easy to write down Carmichael ideals in

_K

: for any prime number ''p'' that splits completely in ''K'', 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

_K

. For example, if ''p'' is any prime number that is 1 mod 4, the ideal (''p'') 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 /ma ...

s Z 'i''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

n

, it is true that

p + 1 \mid n + 1

. 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 ''n'' with the property that for every prime factor ''p'' of ''n'', ''p'' + ''b'' divides ''n'' + ''b'' positively with ''b'' being any integer besides 0. If ''b'' = −1, these are Carmichael numbers, and if ''b'' = 1, 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 those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal n ...

''n'' is a

''m'' with the property that each ''i'' < ''m''

coprime In mathematics, 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 equivale ...

to ''m'' satisfies

i^ \equiv 1 \pmod

. The ''n'' = 1 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. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The term ''a ...

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

ring Ring 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 :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...

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

algebra Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics. Elementary a ...

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 Module, modular and modularity may refer to the concept of modularity. They may also refer to: Computing and engineering * Modular design, the engineering discipline of designing complex devices using separately designed sub-components * Modul ...

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 MathematicsTable of Carmichael numbersTables of Carmichael numbers with many prime factors
* *

{{Classes of natural numbers Integer sequences Modular arithmetic Pseudoprimes