Editing Carmichael number (section)

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