Korselt criterion
= Korselt criterion
{c}
{title2=$N\text{ squarefree},\ p-1\mid N-1\ (p\mid N)$}
A composite <integer> $N>1$ is a <Carmichael number> if and only if it is a <squarefree integer> and
$$
p-1\mid N-1\qquad\text{for every prime }p\mid N.
$$
The criterion is named for <Alwin Korselt>. The two requirements are different: the first excludes repeated <prime factors>, while the second makes the exponent $N-1$ a common multiple of the prime-field return exponents.<Carmichael Numbers and Korselt's Criterion by Keith Conrad>[Theorem 2 (Korselt), printed p. 2]{ref}
For $1105=5\cdot13\cdot17$, the numbers $4,12,16$ divide $1104$ with quotients $276,92,69$. Thus \b[1105 is another <Carmichael number>]. By contrast $341=11\cdot31$ is squarefree, but $30\nmid340$; a single failed divisor condition excludes it. This illustrates the appeal of the criterion: a statement about every <unit> becomes a small calculation using a known <prime factorization>.
The composite condition must be retained. A <prime number> is squarefree and satisfies the divisibility condition, but is excluded from the definition of a <Carmichael number>. The resulting certificate also depends on the supplied factors really being <prime numbers>; merely finding a product decomposition is insufficient.