Editing Carmichael number (section)

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