Editing Carmichael number (section)

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