# Korselt's Theorem

## Contents

## Theorem

Let $n \ge 2$ be an integer.

Then $n$ is a **Carmichael number** if and only if:

- $(1): \quad n$ is odd

and the following conditions hold for every prime factor $p$ of $n$:

- $(2): \quad p^2 \nmid n$
- $(3): \quad \paren {p - 1} \divides \paren {n - 1}$

where:

- $\divides$ denotes divisibility
- $\nmid$ denotes non-divisibility.

## Proof

### Sufficient Condition

Let $n$ be a Carmichael number:

- $(4): \quad \forall a \in \Z: a \perp n: a^n \equiv a \pmod n$

where $\perp$ denotes coprimality.

Suppose $n$ is even.

Set $a = -1$ in $(4)$.

Then $\paren {-1}^n = 1$ and so:

- $1 \equiv -1 \pmod n$

resulting in $n = 2$.

But as $2$ is not a Carmichael number, it follows that for $n$ to be Carmichael it must be odd.

Thus:

- $(1): n$ is odd

holds.

From the Fundamental Theorem of Arithmetic, let $n$ be expressed as:

- $n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$

where:

- the $p_i$'s are distinct odd primes
- for all $i$, $k_i \ge 1$.

By Integers with Primitive Roots there exists a primitive root $a_i$ modulo $p_i^{k_i}$ for each $i$.

In particular, we have that $a_i \perp p_i$.

By the Chinese Remainder Theorem:

- $\exists a: \forall i: a \equiv a_i \pmod {p_i^{k_i} }, a \perp n$

Consider a particular $i$.

We have:

\(\displaystyle a^n\) | \(\equiv\) | \(\displaystyle a \pmod n\) | $\quad$ from $(4)$ | $\quad$ | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle a^{n - 1}\) | \(\equiv\) | \(\displaystyle 1 \pmod n\) | $\quad$ | $\quad$ | ||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle a^{n - 1}\) | \(\equiv\) | \(\displaystyle 1 \pmod {p_i^{k_i} }\) | $\quad$ | $\quad$ | ||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle {a_i}^{n - 1}\) | \(\equiv\) | \(\displaystyle 1 \pmod {p_i^{k_i} }\) | $\quad$ | $\quad$ |

We have that $a_i$ is a primitive root modulo $p_i^{k_i}$.

Thus:

\(\displaystyle \map {\operatorname {ord}_{p_i^{k_i} } } {a_i}\) | \(=\) | \(\displaystyle \map \phi {p_i^{k_i} }\) | $\quad$ where $\phi$ is the Euler $\phi$ function | $\quad$ | |||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle p_i^{k_i - 1} \paren {p_i - 1}\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \) | \(\divides\) | \(\displaystyle n - 1\) | $\quad$ | $\quad$ |

But because $p_i \divides n$:

- $p_i \perp n - 1$

Thus:

- $k_i = 1$

giving that $n$ is square-free, and:

- $p_i - 1 \divides n - 1$

As $i$ is arbitrary, both conditions $(1)$ and $(2)$ of the statement of the theorem are thus fulfilled:

That is:

- $(1): n$ is odd

and for all primes $p$ such that $p \divides n$:

- $(2): \quad p^2 \nmid n$
- $(3): \quad \paren {p - 1} \divides \paren {n - 1}$

$\Box$

### Necessary Condition

Suppose $n$ is such that:

- $(1): n$ is odd

and for all primes $p$ such that $p \divides n$:

- $(2): \quad p^2 \nmid n$
- $(3): \quad \paren {p - 1} \divides \paren {n - 1}$

Thus:

- $n = p_1 p_2 \cdots p_r$

is the product of $r$ distinct odd primes such that:

- $\paren {p_i - 1} \divides \paren {n - 1}$

for all $i$.

Let $a \in \Z$.

Let $a \perp p_i$.

Then by Fermat's Little Theorem:

- $a^{p_i - 1} \equiv 1 \pmod {p_i}$

Thus:

- $a^{n - 1} \equiv 1 \pmod {p_i}$

and so:

- $a^n \equiv a \pmod {p_i}$

Let $\gcd \set {a, p_i} > 1$.

Then as $p_i$ is prime:

- $p_i \divides a$

and so:

- $a^n \equiv a \equiv 0 \pmod {p_i}$

Thus for all $i$ and for all $a \in \Z$:

- $a^n \equiv a \pmod {p_i}$

From the Chinese Remainder Theorem:

- $a^n \equiv a \pmod n$

for all $a$.

Thus, by definition, $n$ is a Carmichael number.

$\blacksquare$

## Also known as

**Korselt's theorem** is also seen referred to as **Korselt's criterion**.

## Source of Name

This entry was named for Alwin Reinhold Korselt.

## Historical Note

Alwin Reinhold Korselt first demonstrated this result in $1899$, but did not actually identify any integers that fulfilled the criterion.

That did not happen until Robert Daniel Carmichael found that $561$ was such a number in $1910$.

It turns out that Václav Šimerka had already found the first $7$ Carmichael numbers in $1885$, but his work was not noticed at the time.

## Sources

- 1986: David Wells:
*Curious and Interesting Numbers*... (previous) ... (next): $561$ - 1997: David Wells:
*Curious and Interesting Numbers*(2nd ed.) ... (previous) ... (next): $561$