Korselt's Theorem

A composite number \( n \) is a Carmichael number if and only if it satisfies the following three conditions:

\( n \) is square-free, meaning no prime \( p \) exists such that \( p^2 \) divides \( n \).
\( n \) is the product of at least three distinct prime numbers, meaning it can be expressed as \( n = p_1 p_2 \dots p_k \) with \( k \geq 2 \).
For every prime divisor \( p_i \) of \( n \), the following holds: \[ p_i - 1 \mid n - 1 \] In other words, \( p_i - 1 \) must be a divisor of \( n - 1 \).

Korselt's theorem provides a way to identify Carmichael numbers without having to check Fermat’s condition for every base \( a \).

A Carmichael number is a composite number \( n \) that satisfies Fermat’s condition for all prime bases \( a \) that are coprime to \( n \), namely:

\[ a^{n-1} \equiv 1 \pmod{n} \]

In particular, the third condition of the theorem implies that all prime factors of \( n \) must be congruent to 1 modulo a common divisor of \( n - 1 \).

Example

The smallest Carmichael number is 561, which satisfies all three conditions of Korselt's theorem.

It is square-free because \( 561 = 3 \times 11 \times 17 \), and none of its prime factors appear squared.
561 is the product of at least three distinct prime numbers.
Each prime factor’s \( p - 1 \) divides \( n - 1 = 560 \):
- 2 (i.e., \( 3 - 1 \)) divides 560
- 10 (i.e., \( 11 - 1 \)) divides 560
- 16 (i.e., \( 17 - 1 \)) divides 560

Here are some additional examples of Carmichael numbers with three or four prime factors:

1105 = 5 × 13 × 17 ( 4 ∣ 1104 ; 12 ∣ 1104 ; 16 ∣ 1104 )
1729 = 7 × 13 × 19 ( 6 ∣ 1728 ; 12 ∣ 1728 ; 18 ∣ 1728 )
2465 = 5 × 17 × 29 ( 4 ∣ 2464 ; 16 ∣ 2464 ; 28 ∣ 2464 )
2821 = 7 × 13 × 31 ( 6 ∣ 2820 ; 12 ∣ 2820 ; 30 ∣ 2820 )
6601 = 7 × 23 × 41 ( 6 ∣ 6600 ; 22 ∣ 6600 ; 40 ∣ 6600 )
8911 = 7 × 19 × 67 ( 6 ∣ 8910 ; 18 ∣ 8910 ; 66 ∣ 8910 )
41041 = 7 × 11 × 13 × 41 ( 6 ∣ 41040 ; 10 ∣ 41040 ; 12 ∣ 41040 ; 40 | 41040 )

Here, \( a \mid b \) means that \( a \) divides \( b \). For example, \( 4 \mid 1104 \) means that 4 is a divisor of 1104.

Each of these numbers meets all three conditions of Korselt’s theorem.

Notes

Some additional observations about this theorem:

All Carmichael numbers are odd
If \( n \) were even and had an odd prime factor \( p \), then \( p - 1 \) would be even, which cannot divide \( n - 1 \) since \( n - 1 \) is odd. This means that every Carmichael number must necessarily be odd.

And so on...