Editing Carmichael number

{{short description|Composite number in number theory}}

In [[number theory]], a '''Carmichael number''' is a [[composite number]] {{tmath|1= n }} which in [[modular arithmetic]] satisfies the [[congruence relation]]:
: <math>b^n\equiv b\pmod{n}</math>
for all integers {{tmath|1= b }}.<ref>{{cite book | last=Riesel | first=Hans | title=Prime Numbers and Computer Methods for Factorization 
| publisher=Birkhäuser | location=Boston, MA | edition=second | year=1994 | isbn=978-0-8176-3743-9 
| zbl=0821.11001 | series=Progress in Mathematics | volume=126 |author-link=Hans Riesel }}</ref> The relation may also be expressed<ref>
{{cite book |last1=Crandall|first1=Richard |last2=Pomerance |first2=Carl |date=2005 |title=Prime Numbers: A Computational Perspective |edition=second |location=New York |publisher=Springer |pages=133–134 |isbn=978-0387-25282-7 |author-link1=Richard Crandall |author-link2=Carl Pomerance }}</ref> in the form:
: <math>b^{n-1}\equiv 1\pmod{n}</math>
for all integers <math>b</math> that are [[relatively prime]] to {{tmath|1= n }}. They are [[infinite set|infinite]] in number.<ref name="Alford-1994">{{cite journal |author=W. R. Alford |author2=Andrew Granville |author3-link=Carl Pomerance |author3=Carl Pomerance |title=There are Infinitely Many Carmichael Numbers |journal=[[Annals of Mathematics]] |volume=140 |year=1994 |issue=3 |pages=703–722 |doi=10.2307/2118576 |url=http://www.math.dartmouth.edu/~carlp/PDF/paper95.pdf |archive-url=https://web.archive.org/web/20050304203448/http://math.dartmouth.edu/~carlp/PDF/paper95.pdf |archive-date=2005-03-04 |url-status=live|jstor=2118576 |author2-link=Andrew Granville |author-link=W. R. (Red) Alford }}</ref>

[[File:Robert Daniel Carmichael.gif|thumb|257x257px|[[Robert Daniel Carmichael]]]]

They constitute the comparatively rare instances where the strict converse of [[Fermat's Little Theorem]] does not hold.  This fact precludes the use of that theorem as an absolute test of [[Prime numbers|primality]].<ref name="Cepelewicz-2022">{{cite web |last=Cepelewicz |first=Jordana |date=13 October 2022 |title=Teenager Solves Stubborn Riddle About Prime Number Look-Alikes |url=https://www.quantamagazine.org/teenager-solves-stubborn-riddle-about-prime-number-look-alikes-20221013/ |website=Quanta Magazine |access-date=13 October 2022}}</ref>

The Carmichael numbers form the subset ''K''<sub>1</sub> of the [[Knödel number]]s.

The Carmichael numbers were named after the American mathematician [[Robert Daniel Carmichael|Robert Carmichael]] by [[N. G. W. H. Beeger|Nicolaas Beeger]], in 1950. [[Øystein Ore]] had referred to them in 1948 as numbers with the "Fermat property", or "''F'' numbers" for short.<ref>{{cite book |last=Ore |first=Øystein |author-link=Øystein Ore |url=https://archive.org/details/numbertheoryitsh00ore/page/331/mode/1up |title=Number Theory and Its History |date=1948 |publisher=McGraw-Hill |location=New York |pages=331–332 |url-access=registration |via=[[Internet Archive]]}}</ref>

== Overview ==
[[Fermat's little theorem]] states that if <math>p</math> is a [[prime number]], then for any [[integer]] {{tmath|1= b }}, the number <math>b^p-b</math> is an integer multiple of {{tmath|1= p }}.  Carmichael numbers are composite numbers which have the same property.  Carmichael numbers are also called [[Fermat pseudoprime]]s or '''absolute Fermat pseudoprimes'''. A Carmichael number will pass a [[Fermat primality test]] to every base <math>b</math> 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 pseudoprime|strong probable prime]] tests such as the [[Baillie–PSW primality test]] and the [[Miller–Rabin primality test]].

However, no Carmichael number is either an [[Euler–Jacobi pseudoprime]] or a [[strong pseudoprime]] to every base relatively prime to it<ref>
{{cite journal |author=D. H. Lehmer |author-link=Derrick Henry Lehmer |title=Strong Carmichael numbers |journal=J. Austral. Math. Soc. |date=1976 |volume=21 |issue=4 |pages=508–510 |doi=10.1017/s1446788700019364|doi-access=free }} Lehmer proved that no Carmichael number is an Euler-Jacobi pseudoprime to every base relatively prime to it. He used the term ''strong pseudoprime'', but the terminology has changed since then. Strong pseudoprimes are a subset of Euler-Jacobi pseudoprimes. Therefore, no Carmichael number is a strong pseudoprime to every base relatively prime to it.</ref>
so, in theory, either an Euler or a strong probable prime test could prove that a Carmichael number is, in fact, composite.

Arnault<ref name="Arnault397Digit">
{{cite journal|title=Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases|journal=Journal of Symbolic Computation|date=August 1995|volume=20|issue=2|pages=151–161
|author=F. Arnault|doi=10.1006/jsco.1995.1042|doi-access=free}}</ref>
gives a 397-digit Carmichael number <math>N</math> that is a ''strong'' pseudoprime to all ''prime'' bases less than 307:
: <math>N =  p \cdot (313(p - 1) + 1) \cdot (353(p - 1) + 1 )</math>
where
: <math>p = </math>{{hsp}}2{{hsp}}9674495668{{hsp}}6855105501{{hsp}}5417464290{{hsp}}5332730771{{hsp}}9917998530{{hsp}}4335099507{{hsp}}5531276838{{hsp}}7531717701{{hsp}}9959423859{{hsp}}6428121188{{hsp}}0336647542{{hsp}}1834556249{{hsp}}3168782883<br />
is a 131-digit prime. <math>p</math> is the smallest prime factor of {{tmath|1= N }}, so this Carmichael number is also a (not necessarily strong) pseudoprime to all bases less than {{tmath|1= p }}.

As numbers become larger, Carmichael numbers become increasingly rare. For example, there are 20,138,200 Carmichael numbers between 1 and 10<sup>21</sup> (approximately one in 50 trillion (5·10<sup>13</sup>) numbers).<ref name="Pinch2007">
{{cite conference |url=http://tucs.fi/publications/attachment.php?fname=G46.pdf
 |title=The Carmichael numbers up to 10<sup>21</sup> |last=Pinch |first=Richard |date=December 2007
 |editor=Anne-Maria Ernvall-Hytönen |volume=46
 |publisher=Turku Centre for Computer Science |pages=129–131 |location=Turku, Finland
 |conference=Proceedings of Conference on Algorithmic Number Theory
 |access-date=2017-06-26
}}</ref>

=== Korselt's criterion ===
An alternative and equivalent definition of Carmichael numbers is given by '''Korselt's criterion'''.

: '''Theorem''' ([[Alwin Korselt|A. Korselt]] 1899): A positive composite integer <math>n</math> is a Carmichael number if and only if <math>n</math> is [[square-free integer|square-free]], and for all [[prime divisor]]s <math>p</math> of {{tmath|1= n }}, it is true that {{tmath|1= p - 1 \mid n - 1 }}.

It follows from this theorem that all Carmichael numbers are [[parity (mathematics)|odd]], since any [[parity (mathematics)|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 <math>p-1  \mid n-1</math> results in an even dividing an odd, a contradiction. (The oddness of Carmichael numbers also follows from the fact that <math>-1</math> is a [[Fermat primality test|Fermat witness]] for any even composite number.)
From the criterion it also follows that Carmichael numbers are [[Cyclic number (group theory)|cyclic]].<ref>[http://www.numericana.com/data/crump.htm Carmichael Multiples of Odd Cyclic Numbers] "Any divisor of a Carmichael number must be an odd cyclic number"</ref><ref>Proof sketch: If <math>n</math> is square-free but not cyclic, <math>p_i \mid p_j - 1</math> for two prime factors <math>p_i</math> and <math>p_j</math> of <math>n</math>. But if <math>n</math> satisfies Korselt then {{tmath|1= p_j - 1  \mid n - 1 }}, so by transitivity of the "divides" relation {{tmath|1= p_i  \mid n - 1 }}. But <math>p_i</math> is also a factor of {{tmath|1= n }}, a contradiction.</ref> 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]] in 1885<ref name="Simerka1885">{{cite journal |last1=Šimerka|first1=Václav|author-link1=Václav Šimerka|title=Zbytky z arithmetické posloupnosti|trans-title=On the remainders of an arithmetic progression|journal=Časopis pro pěstování mathematiky a fysiky |volume=14 |issue=5|year=1885 |pages=221–225 |doi=10.21136/CPMF.1885.122245 |url=http://dml.cz/handle/10338.dmlcz/122245|doi-access=free }}</ref> (thus preceding not just Carmichael but also Korselt, although Šimerka did not find anything like Korselt's criterion).<ref>{{cite journal |last1=Lemmermeyer |first1=F. |title=Václav Šimerka: quadratic forms and factorization |journal=LMS Journal of Computation and Mathematics |date=2013 |volume=16 |pages=118–129 |doi=10.1112/S1461157013000065 |doi-access=free}}</ref> His work, published in Czech scientific journal ''[[Časopis pro pěstování matematiky a fysiky]]'', however, remained unnoticed.[[File:Vaclav Simerka.jpg|thumb|Václav Šimerka listed the first seven Carmichael numbers]]

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, <math>561 = 3 \cdot 11 \cdot 17</math> is square-free and {{tmath|1= 2 \mid 560 }}, <math>10 \mid 560</math> and {{tmath|1= 16 \mid 560 }}.
The next six Carmichael numbers are {{OEIS|id=A002997}}:
: <math>1105 = 5 \cdot 13 \cdot 17 \qquad (4 \mid 1104;\quad 12 \mid 1104;\quad 16 \mid 1104)</math>
: <math>1729 = 7 \cdot 13 \cdot 19 \qquad (6 \mid 1728;\quad 12 \mid 1728;\quad 18 \mid 1728)</math>
: <math>2465 = 5 \cdot 17 \cdot 29 \qquad (4 \mid 2464;\quad 16 \mid 2464;\quad 28 \mid 2464)</math>
: <math>2821 = 7 \cdot 13 \cdot 31 \qquad (6 \mid 2820;\quad 12 \mid 2820;\quad 30 \mid 2820)</math>
: <math>6601 = 7 \cdot 23 \cdot 41 \qquad (6 \mid 6600;\quad 22 \mid 6600;\quad 40 \mid 6600)</math>
: <math>8911 = 7 \cdot 19 \cdot 67 \qquad (6 \mid 8910;\quad 18 \mid 8910;\quad 66 \mid 8910).</math>

In 1910, Carmichael himself<ref name="Carmichael1910">{{cite journal |author=R. D. Carmichael|title=Note on a new number theory function |journal=Bulletin of the American Mathematical Society |volume=16 |issue=5|year=1910 |pages=232–238 |url=https://www.ams.org/journals/bull/1910-16-05/home.html |doi=10.1090/s0002-9904-1910-01892-9|doi-access=free }}</ref> also published the smallest such number, 561, and the numbers were later named after him.

[[Jack Chernick]]<ref name="Chernick1939">{{cite journal |author=Chernick, J. |title=On Fermat's simple theorem |journal=Bull. Amer. Math. Soc. |volume=45 |issue=4 |year=1939 |pages=269–274 |doi=10.1090/S0002-9904-1939-06953-X  |url=https://www.ams.org/journals/bull/1939-45-04/S0002-9904-1939-06953-X/S0002-9904-1939-06953-X.pdf|doi-access=free }}</ref> proved a theorem in 1939 which can be used to construct a [[subset]] of Carmichael numbers. The number <math>(6k + 1)(12k + 1)(18k + 1)</math> 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]]).

[[Paul Erdős]] heuristically argued there should be infinitely many Carmichael numbers. In 1994 [[W. R. (Red) Alford]], [[Andrew Granville]] and [[Carl Pomerance]]  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 <math>n</math>, there are at least <math>n^{2/7}</math> Carmichael numbers between 1 and {{tmath|1= n }}.<ref name="Alford-1994" />

[[Thomas Wright (mathematician)|Thomas Wright]] proved that if <math>a</math> and <math>m</math> are relatively prime,
then there are infinitely many Carmichael numbers in the [[arithmetic progression]] {{tmath|1= a + k \cdot m }},
where {{tmath|1= k = 1, 2, \ldots }}.<ref>{{cite journal |author=Thomas Wright |title=Infinitely many Carmichael Numbers in Arithmetic Progressions |journal=[[Bull. London Math. Soc.]] |volume=45 |year=2013 |issue=5 |pages=943–952 |arxiv=1212.5850 |doi=10.1112/blms/bdt013|s2cid=119126065 }}</ref>

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,<ref>{{cite journal |author1=W.R. Alford|author2=Jon Grantham|author3=Steven Hayman|author4=Andrew Shallue |display-authors=1|title=Constructing Carmichael numbers through improved subset-product algorithms|journal=Math. Comp.|volume=83|year=2014|issue=286|pages=899–915|arxiv=1203.6664|doi=10.1090/S0025-5718-2013-02737-8|s2cid=35535110|author-link=W. R. (Red) Alford}}</ref> so the largest known Carmichael number is much greater than the [[largest known prime]].

== Properties ==

=== Factorizations ===
Carmichael numbers have at least three positive prime factors. The first Carmichael numbers with <math>k = 3, 4, 5, \ldots</math> prime factors are {{OEIS|id=A006931}}:

{| class="wikitable"
|-
! ''k'' !! &nbsp;
|-
| 3 || <math>561 = 3 \cdot 11 \cdot 17\,</math>
|-
| 4 || <math>41041 = 7 \cdot 11 \cdot 13 \cdot 41\,</math>
|-
| 5 || <math>825265 = 5 \cdot 7 \cdot 17 \cdot 19 \cdot 73\,</math>
|-
| 6 || <math>321197185 = 5 \cdot 19 \cdot 23 \cdot 29 \cdot 37 \cdot 137\,</math>
|-
| 7 || <math>5394826801 = 7 \cdot 13 \cdot 17 \cdot 23 \cdot 31 \cdot 67 \cdot 73\,</math>
|-
| 8 || <math>232250619601 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 31 \cdot 37 \cdot 73 \cdot 163\,</math>
|-
| 9 || <math>9746347772161 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 31 \cdot 37 \cdot 41 \cdot 641\,</math>
|}

The first Carmichael numbers with 4 prime factors are {{OEIS|id=A074379}}:

{| class="wikitable"
|-
! ''i'' !!&nbsp;
|-
| 1 || <math>41041 = 7 \cdot 11 \cdot 13 \cdot 41\,</math>
|-
| 2 || <math>62745 = 3 \cdot 5 \cdot 47 \cdot 89\,</math>
|-
| 3 || <math>63973 = 7 \cdot 13 \cdot 19 \cdot 37\,</math>
|-
| 4 || <math>75361 = 11 \cdot 13 \cdot 17 \cdot 31\,</math>
|-
| 5 || <math>101101 = 7 \cdot 11 \cdot 13 \cdot 101\,</math>
|-
| 6 || <math>126217 = 7 \cdot 13 \cdot 19 \cdot 73\,</math>
|-
| 7 || <math>172081 = 7 \cdot 13 \cdot 31 \cdot 61\,</math>
|-
| 8 || <math>188461 = 7 \cdot 13 \cdot 19 \cdot 109\,</math>
|-
| 9 || <math>278545 = 5 \cdot 17 \cdot 29 \cdot 113\,</math>
|-
| 10 || <math>340561 = 13 \cdot 17 \cdot 23 \cdot 67\,</math>
|}

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 [[1729 (number)|Hardy-Ramanujan Number]]: the smallest number that can be expressed as the [[sum of two cubes]] (of positive numbers) in two different ways.

=== Distribution ===

Let <math>C(X)</math> denote the number of Carmichael numbers less than or equal to {{tmath|1= X }}. The distribution of Carmichael numbers by powers of 10 {{OEIS|id=A055553}}:<ref name="Pinch2007"/>

{| class="wikitable" style="margin:1em auto;"
|-
! <math>n</math>
|  1
|  2
|  3
|  4
|  5
|  6
|  7
|  8
|  9
| 10
| 11
| 12
| 13
| 14
| 15
| 16
| 17
| 18
| 19
| 20
| 21
|-
! <math>C(10^n)</math>
|        0
|        0
|        1
|        7
|       16
|       43
|      105
|      255
|      646
|     1547
|     3605
|     8241
|    19279
|    44706
|   105212
|   246683
|   585355
|  1401644
|  3381806
|  8220777
| 20138200
|}
In 1953, [[Walter Knödel|Knödel]] proved the [[Upper and lower bounds|upper bound]]:
: <math>C(X) < X \exp\left({-k_1 \left( \log X \log \log X\right)^\frac{1}{2}}\right)</math>
for some constant {{tmath|1= k_1 }}.

In 1956, Erdős improved the bound to
: <math>C(X) < X \exp\left(\frac{-k_2 \log X \log \log \log X}{\log \log X}\right)</math>
for some constant {{tmath|1= k_2 }}.<ref name="Erdős1956">{{cite journal |author=Erdős, P. |year=2022 |title=On pseudoprimes and Carmichael numbers |journal=Publ. Math. Debrecen |volume=4 |issue=3–4 |pages=201–206 |doi=10.5486/PMD.1956.4.3-4.16 |url=http://www.renyi.hu/~p_erdos/1956-10.pdf |archive-url=https://web.archive.org/web/20110611160632/http://www.renyi.hu/~p_erdos/1956-10.pdf |archive-date=2011-06-11 |url-status=live |mr=79031 |s2cid=253789521 |author-link=Paul Erdős }}</ref> He further gave a [[heuristic argument]] suggesting that this upper bound should be close to the true growth rate of {{tmath|1= C(X) }}.

In the other direction, [[W. R. (Red) Alford|Alford]], [[Andrew Granville|Granville]] and [[Carl Pomerance|Pomerance]] proved in 1994<ref name="Alford-1994" /> that for [[Eventually (mathematics)|sufficiently large]] ''X'',
: <math>C(X) > X^\frac{2}{7}.</math>

In 2005, this bound was further improved by [[Glyn Harman|Harman]]<ref>{{cite journal |author=Glyn Harman |title=On the number of Carmichael numbers up to ''x'' |journal=Bulletin of the London Mathematical Society |volume=37 |issue=5 |year=2005 |pages=641–650 |doi=10.1112/S0024609305004686|s2cid=124405969 }}</ref> to
: <math>C(X) > X^{0.332}</math>
who subsequently improved the exponent to {{tmath|1= 0.7039 \cdot 0.4736 = 0.33336704 > 1/3 }}.<ref>
{{cite journal |last=Harman |first=Glyn
 |date=2008 |title=Watt's mean value theorem and Carmichael numbers
 |doi=10.1142/S1793042108001316 |mr=2404800
 |journal=International Journal of Number Theory |volume=4 |issue=2 |pages=241–248
}}</ref>

Regarding the asymptotic distribution of Carmichael numbers, there have been several conjectures. In 1956, Erdős<ref name="Erdős1956"/> conjectured that there were <math>X^{1-o(1)}</math> Carmichael numbers for ''X'' sufficiently large. In 1981, Pomerance<ref name="Pomerance1981">{{cite journal |author=Pomerance, C. |year=1981 |title=On the distribution of pseudoprimes |journal=Math. Comp. |volume=37 |issue=156 |pages=587–593|jstor=2007448 |doi=10.1090/s0025-5718-1981-0628717-0|author-link=Carl Pomerance |doi-access=free }}</ref> sharpened Erdős' heuristic arguments to conjecture that there are at least
: <math> X \cdot L(X)^{-1 + o(1)} </math>
Carmichael numbers up to {{tmath|1= X }}, where {{tmath|1= L(x) = \exp{ \left( \frac{\log x \log\log\log x} {\log\log x} \right) } }}.

However, inside current computational ranges (such as the count of Carmichael numbers performed by Goutier{{OEIS|id=A055553}} up to 10<sup>22</sup>), these conjectures are not yet borne out by the data; empirically, the exponent is <math> C(X) \approx X^{0.35}</math> for the highest available count (C(X)=49679870 for X= 10<sup>22</sup>).

<!-- Too indirect and long? -->In 2021, [[Daniel Larsen (mathematician)|Daniel Larsen]] proved an analogue of [[Bertrand's postulate]] for Carmichael numbers first conjectured by Alford, Granville, and Pomerance in 1994.<ref name="Cepelewicz-2022" /><ref>{{cite journal |author=Larsen, Daniel |date=20 July 2022 |title=Bertrand's Postulate for Carmichael Numbers |url=https://academic.oup.com/imrn/advance-article-abstract/doi/10.1093/imrn/rnac203/6647493 |journal=International Mathematics Research Notices |volume=2023 |issue=15 |pages=13072–13098 |arxiv=2111.06963 |doi=10.1093/imrn/rnac203}}</ref> Using techniques developed by [[Yitang Zhang]] and [[James Maynard (mathematician)|James Maynard]] to establish results concerning [[Twin prime conjecture|small gaps between primes]], his work yielded the much stronger statement that, for any <math>\delta>0</math> and sufficiently large <math>x</math> in terms of <math>\delta</math>, there will always be at least  
: <math>\exp{\left(\frac{\log{x}}{(\log \log{x})^{2+\delta}}\right)} </math>
Carmichael numbers between <math>x</math> and
: <math>x+\frac{x}{(\log{x})^{\frac{1}{2+\delta}}}.</math>

== Generalizations ==
The notion of Carmichael number generalizes to a Carmichael ideal in any [[number field]] {{tmath|1= K }}. For any nonzero [[prime ideal]] <math>\mathfrak p</math> in {{tmath|1= {\mathcal O}_K }}, we have <math>\alpha^{{\rm N}(\mathfrak p)} \equiv \alpha \bmod {\mathfrak p}</math> for all <math>\alpha</math> in {{tmath|1= {\mathcal O}_K }}, where <math>{\rm N}(\mathfrak p)</math> is the norm of the [[Ideal (ring theory)|ideal]] {{tmath|1= \mathfrak p }}. (This generalizes Fermat's little theorem, that <math>m^p \equiv m \bmod p</math> for all integers {{tmath|1= m }} when {{tmath|1= p }} is prime.) Call a nonzero ideal <math>\mathfrak a</math> in <math>{\mathcal O}_K</math> Carmichael if it is not a prime ideal and <math>\alpha^{{\rm N}(\mathfrak a)} \equiv \alpha \bmod {\mathfrak a}</math> for all {{tmath|1= \alpha \in {\mathcal O}_K }}, where <math>{\rm N}(\mathfrak a)</math> is the norm of the ideal {{tmath|1= \mathfrak a }}.  When {{tmath|1= K }} is {{tmath|1= \mathbf Q }}, the ideal <math>\mathfrak a</math> is [[Principal ideal|principal]], and if we let {{tmath|1= a }} be its positive generator then the ideal <math>\mathfrak a = (a)</math> is Carmichael exactly when {{tmath|1= a }} is a Carmichael number in the usual sense.

When {{tmath|1= K }} is larger than the [[Rational number|rational]]s it is easy to write down Carmichael ideals in {{tmath|1= {\mathcal O}_K }}: for any prime number {{tmath|1= p }} that splits completely in {{tmath|1= K }}, the principal ideal <math>p{\mathcal O}_K</math> is a Carmichael ideal. Since infinitely many prime numbers split completely in any number field, there are infinitely many Carmichael ideals in {{tmath|1= {\mathcal O}_K }}. For example, if {{tmath|1= p }} is any prime number that is 1 mod 4, the ideal {{tmath|1= (p) }} in the [[Gaussian integer]]s <math>\mathbb Z[i]</math> is a Carmichael ideal.

Both prime and Carmichael numbers satisfy the following equality:
: <math>\gcd \left(\sum_{x=1}^{n-1} x^{n-1}, n\right) = 1.</math>

== Lucas–Carmichael number ==
{{main|Lucas–Carmichael number}}

A positive composite integer <math>n</math> is a Lucas–Carmichael number if and only if <math>n</math> is [[square-free integer|square-free]], and for all [[prime divisor]]s <math>p</math> of {{tmath|1= n }}, it is true that {{tmath|1= 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, ... {{OEIS|A006972}}

== Quasi–Carmichael number ==

Quasi–Carmichael numbers are squarefree composite numbers {{tmath|1= n }} with the property that for every prime factor {{tmath|1= p }} of {{tmath|1= n }}, {{tmath|1= p + b }} divides {{tmath|1= n + b }} positively with {{tmath|1= b }} being any integer besides 0. If {{tmath|1= b = -1 }}, these are Carmichael numbers, and if {{tmath|1= 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, ... {{OEIS|A257750}}

== Knödel number==
{{main|Knödel number}}

An ''n''-'''Knödel number''' for a given [[positive integer]] ''n'' is a [[composite number]] ''m'' with the property that each {{tmath|1= i < m }} [[coprime]] to ''m'' satisfies {{tmath|1= i^{m - n} \equiv 1 \pmod{m} }}. The {{tmath|1= n = 1 }} case are Carmichael numbers.

== 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 ''n''th-power-raising function ''p''<sub>''n''</sub> from the [[ring (mathematics)|ring]] '''Z'''<sub>''n''</sub> of integers modulo ''n'' to itself is the identity function. The identity is the only '''Z'''<sub>''n''</sub>-[[algebra over a field|algebra]] [[endomorphism]] on '''Z'''<sub>''n''</sub> so we can restate the definition as asking that ''p''<sub>''n''</sub> be an algebra endomorphism of '''Z'''<sub>''n''</sub>.
As above, ''p''<sub>''n''</sub> satisfies the same property whenever ''n'' is prime.

The ''n''th-power-raising function ''p''<sub>''n''</sub> is also defined on any '''Z'''<sub>''n''</sub>-algebra '''A'''. A theorem states that ''n'' is prime if and only if all such functions ''p''<sub>''n''</sub> 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''<sub>''n''</sub> is an endomorphism on every '''Z'''<sub>''n''</sub>-algebra that can be generated as '''Z'''<sub>''n''</sub>-[[module (mathematics)|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.<ref>{{cite journal |author = Everett W. Howe |title=Higher-order Carmichael numbers |journal=Mathematics of Computation |date=October 2000 |volume=69 |issue=232 |pages=1711–1719 |arxiv=math.NT/9812089 |jstor=2585091 |doi=10.1090/s0025-5718-00-01225-4|bibcode=2000MaCom..69.1711H |s2cid=6102830 }}</ref>

=== 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 ==
{{reflist|40em}}

== References ==
* {{cite journal |author=Carmichael, R. D.|year=1910|title=Note on a new number theory function |journal=[[Bulletin of the American Mathematical Society]] |volume=16 |issue=5|pages=232–238 |url=https://www.ams.org/journals/bull/1910-16-05/home.html |doi=10.1090/s0002-9904-1910-01892-9|doi-access=free }}
* {{cite journal |author=Carmichael, R. D. |year=1912 |title=On composite numbers ''P'' which satisfy the Fermat congruence <math>a^{P-1}\equiv 1\bmod P</math> |journal=[[American Mathematical Monthly]] |volume=19 |issue=2 |pages=22–27 |doi=10.2307/2972687|jstor=2972687 }}
* {{cite journal |author=Chernick, J. |year=1939 |title=On Fermat's simple theorem |journal=Bull. Amer. Math. Soc. |volume=45 |issue=4 |pages=269–274 |doi=10.1090/S0002-9904-1939-06953-X  |url=https://www.ams.org/journals/bull/1939-45-04/S0002-9904-1939-06953-X/S0002-9904-1939-06953-X.pdf|doi-access=free }}
* {{cite journal |author=Korselt, A. R. |year=1899 |title=Problème chinois |journal=[[L'Intermédiaire des Mathématiciens]] |volume=6 |pages=142–143}}
* {{cite journal |author1=Löh, G. |author2=Niebuhr, W. |year=1996 |url=https://www.ams.org/mcom/1996-65-214/S0025-5718-96-00692-8/S0025-5718-96-00692-8.pdf |archive-url=https://web.archive.org/web/20030425040718/http://www.ams.org/mcom/1996-65-214/S0025-5718-96-00692-8/S0025-5718-96-00692-8.pdf |archive-date=2003-04-25 |url-status=live |title=A new algorithm for constructing large Carmichael numbers |journal=Math. Comp. |volume=65 |issue=214 |pages=823–836 |doi=10.1090/S0025-5718-96-00692-8|bibcode=1996MaCom..65..823L |doi-access=free }}
* {{cite book | title = The Book of Prime Number Records | publisher = Springer | year = 1989 | isbn = 978-0-387-97042-4 | author = Ribenboim, P. | author-link = Paulo Ribenboim }}
* {{cite journal |author=Šimerka, V.|year=1885 |title=Zbytky z arithmetické posloupnosti (On the remainders of an arithmetic progression) |journal=Časopis Pro Pěstování Matematiky a Fysiky |volume=14 |issue=5 |pages=221–225 |doi=10.21136/CPMF.1885.122245 |url=http://dml.cz/handle/10338.dmlcz/122245|doi-access=free }}

== External links ==
* {{springer|title=Carmichael number|id=p/c110100}}
* [https://encyclopediaofmath.org/wiki/Carmichael_number Encyclopedia of Mathematics]
* [https://web.archive.org/web/20090906105152/http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Carmichael-Zahlen Table of Carmichael numbers]
* [https://github.com/drazioti/Carmichael/tree/master/Tables Tables of Carmichael numbers with many prime factors]
* [http://www.s369624816.websitehome.co.uk/rgep/cartable.html Tables of Carmichael numbers below <math>10^{18}</math>]
* {{MathPages|id=home/kmath028/kmath028|title=The Dullness of 1729}}
* {{MathWorld | urlname=CarmichaelNumber | title=Carmichael Number}}
* [http://www.numericana.com/answer/modular.htm Final Answers Modular Arithmetic]

{{Classes of natural numbers}}

[[Category:Eponymous numbers in mathematics]]
[[Category:Integer sequences]]
[[Category:Modular arithmetic]]
[[Category:Pseudoprimes]]