# Carmichael Number has 3 Odd Prime Factors

Jump to navigation Jump to search

## Theorem

Let $n$ be a Carmichael number.

Then $n$ has at least $3$ distinct odd prime factors.

## Proof

By Korselt's Theorem, $n$ is odd.

Therefore $n$ has at least $1$ odd prime factor.

By Korselt's Theorem, for each prime factor of $n$:

$p^2 \nmid n$
$\paren {p - 1} \divides \paren {n - 1}$

Suppose $n = p^k$ for some odd prime $p$.

By Korselt's Theorem, $k = 1$.

However by definition of a Carmichael Number, $n$ cannot be prime.

Therefore $n$ has at least $2$ distinct odd prime factors.

Suppose $n = p^a q^b$ for distinct odd primes $p$ and $q$.

By Korselt's Theorem, the following holds:

$a = b = 1$
$n = p q$
$\paren {p - 1} \divides \paren {n - 1}$
$\paren {q - 1} \divides \paren {n - 1}$

Hence:

 $\ds \paren {p - 1}$ $\divides$ $\ds \paren {n - 1 - q \paren {p - 1} }$ $\ds$ $=$ $\ds p q - 1 - p q + q$ $\ds$ $=$ $\ds q - 1$

Swapping $p$ and $q$ yields $\paren {q - 1} \divides \paren {p - 1}$.

Hence $p - 1 = q - 1$ and $p = q$, which is a contradiction.

Therefore $n$ has at least $3$ distinct odd prime factors.

$\blacksquare$

## Historical Note

Robert Daniel Carmichael proved that a Carmichael Number has at least 3 distinct odd prime factors in $1912$, at around the same time that he discovered that $561$ was the smallest one.