Carmichael Numbers

A Carmichael number is a positive composite integer \( n \) (i.e., not a prime) that behaves like a prime in Fermat’s primality test for every integer \( 1 < a < n \) that is coprime to \( n \), meaning \( \gcd(a, n) = 1 \).

In other words, a Carmichael number satisfies the same property as Fermat’s Little Theorem, which characterizes prime numbers—but without actually being prime.

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

This means \( n \) is a pseudoprime for all numbers \( a \) that are relatively prime to it.

Essentially, it’s a false positive in Fermat’s primality test—it looks prime, but it isn’t.

Note: There are infinitely many Carmichael numbers. The smallest is \( 561 \), followed by \( 1105 \), \( 1729 \), \( 2465 \), \( 2821 \), and so on.

A Practical Example

One of the most well-known Carmichael numbers is \( n = 561 \). It’s the smallest Carmichael number and is the product of three distinct prime numbers:

\[ 561 = 3 \times 11 \times 17. \]

Even though \( 561 \) is not a prime, it still satisfies the condition of being a "strong pseudoprime" for all values of \( a \) that are coprime to \( 561 \), meaning it passes Fermat’s primality test:

\[ a^{560} \equiv 1 \pmod{561}\]

To verify this, we consider all coprime numbers to \( n = 561 \), which are the integers \( 1 < a < 561 \) that have no common divisors with 561 (i.e., \( \gcd(a, 561) = 1 \)).

\[ \gcd(a,561) = 1 \]

The numbers coprime to \( 561 \) are those that are not multiples of 3, 11, or 17—the prime factors of 561.

\[ 2, 4, 5, 7, 8, 10, 13, 14, 16, 19, .... , 559, 560 \]

All these values of \( a \) satisfy the condition \( \gcd(a,560) = 1 \).

Now, let’s check if they are also pseudoprimes for 561. To be pseudoprimes, they must satisfy Fermat’s theorem:

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

Base	Fermat’s Test	561 is Pseudoprime for This Base
\( a = 2 \)	\( 2^{560} \equiv 1 \pmod{561} \)	✅ yes
\( a = 4 \)	\( 4^{560} \equiv 1 \pmod{561} \)	✅ yes
\( a = 5 \)	\( 5^{560} \equiv 1 \pmod{561} \)	✅ yes
\( a = 7 \)	\( 7^{560} \equiv 1 \pmod{561} \)	✅ yes
\( a = 10 \)	\( 10^{560} \equiv 1 \pmod{561} \)	✅ yes
\( a = 13 \)	\( 13^{560} \equiv 1 \pmod{561} \)	✅ yes
\( a = 14 \)	\( 14^{560} \equiv 1 \pmod{561} \)	✅ yes
\( a = 16 \)	\( 16^{560} \equiv 1 \pmod{561} \)	✅ yes
\( a = 19 \)	\( 19^{560} \equiv 1 \pmod{561} \)	✅ yes
...	...	...
\( a = 559 \)	\( 559^{560} \equiv 1 \pmod{561} \)	✅ yes
\( a = 560 \)	\( 560^{560} \equiv 1 \pmod{561} \)	✅ yes

This confirms that every number coprime to \( n=561 \) is also a pseudoprime for \( n \).

Note: Instead of checking every individual number against Fermat’s theorem, there’s a much quicker way to verify this property. A number \( n \) is guaranteed to be a Carmichael number if it meets these two conditions:

• It has at least three distinct prime factors.
• For each prime factor \( p_i \), \( p_i - 1 \) divides \( n - 1 \).

This explains why \( 561 \) is a false positive for Fermat’s primality test and why it falls into the category of Carmichael numbers.

To avoid Carmichael numbers, more reliable primality tests are needed, such as the Miller-Rabin test or the Baillie-PSW test.

Korselt’s Criterion

Korselt’s criterion (or theorem) offers a straightforward method for identifying Carmichael numbers without the need to test every possible base individually.

These conditions ensure that \( n \) satisfies the property \( a^{n-1} \equiv 1 \pmod{n} \) for all \( a \) coprime to \( n \) without requiring individual verification for each base.

Example

The smallest Carmichael number is \( 561 \).

It is a composite number with three distinct prime factors:

\[ 561 = 3 \times 11 \times 17 \]

None of these primes appear more than once in the factorization.

Now, let's verify whether \( 561 \) satisfies the condition \( p_i - 1 \mid n - 1 \) for each of its prime factors:

• For \( p_i = 3 \), we check \( 2 \mid 560 \):
  Since 2 divides 560, the condition holds.
• For \( p_i = 11 \), we check \( 10 \mid 560 \):
  Since 10 divides 560, the condition holds.
• For \( p_i = 17 \), we check \( 16 \mid 560 \):
  Since 16 divides 560, the condition holds.

Since this condition is satisfied for all prime factors of \( 561 \), we can conclude that \( 561 \) is indeed a Carmichael number.

Proof

We need to prove that \(n\) is a Carmichael number if and only if, for every prime factor \(p\) of \(n\), the condition \(p - 1 \mid n - 1\) holds—meaning that \(p - 1\) divides \(n - 1\).

It is already known that \(n\) is a Carmichael number if it is composed of distinct prime factors:

\[ n = p_1 \cdot p_2 \cdots p_h \]

where \(p_1, p_2, \dots, p_h\) are the prime factors of \(n\).

By definition, \(n\) is a Carmichael number if, for every integer \(a\) coprime to \(n\) (i.e., \(\gcd(a, n) = 1\)), it satisfies Fermat’s Little Theorem:

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

Now, consider any integer \(a\) such that \(\gcd(a, n) = 1\), meaning \(a\) is coprime to \(n\).

Since \(a\) is coprime to \(n\), it is also coprime to each prime factor \(p_i\) of \(n\).

By Fermat’s Little Theorem, we then have:

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

By assumption, \(p_i - 1\) divides \(n - 1\), so there exists an integer \(k_i\) such that:

\[ n - 1 = k_i \cdot (p_i - 1) \]

Using this, we can rewrite \(a^{n-1}\) as:

\[ a^{n-1} = a^{k_i \cdot (p_i - 1)} = \left(a^{p_i - 1}\right)^{k_i} \]

Since we already established that \(a^{p_i - 1} \equiv 1 \pmod{p_i}\), it follows that:

\[ \left(a^{p_i - 1}\right)^{k_i} \equiv 1^{k_i} \equiv 1 \pmod{p_i} \]

Thus, for each prime factor \(p_i\) of \(n\), we have:

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

Since \(n = p_1 \cdot p_2 \cdots p_h\) is the product of distinct primes, we can apply the Chinese Remainder Theorem to combine the individual congruences:

\[ \begin{cases} a^{n-1} \equiv 1 \pmod{p_1}, \\ a^{n-1} \equiv 1 \pmod{p_2}, \\ \vdots \\ a^{n-1} \equiv 1 \pmod{p_h}. \end{cases} \]

Since the moduli \(p_1, p_2, \dots, p_h\) are pairwise coprime (as they are distinct primes), these congruences can be combined into a single one modulo \(n = p_1 \cdot p_2 \cdots p_h\), according to the Chinese Remainder Theorem.

Since all the individual congruences have the right-hand side equal to \(1\), we conclude:

\[ a^{n-1} \equiv 1 \pmod{p_1 \cdot p_2 \cdots p_h} \]

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

This confirms that if \(p_i - 1 \mid n - 1\) for every prime factor \(p_i\) of \(n\), then \(n\) is a Carmichael number, as it satisfies \(a^{n-1} \equiv 1 \pmod{n}\) for all integers \(a\) coprime to \(n\).

Additional Notes

Here are a few additional insights about Carmichael numbers:

• All Carmichael numbers are odd
  This follows directly from Korselt’s theorem, which requires that \( p-1 \) divides \( n-1 \) for every prime factor \( p \) of \( n \). If \( n \) were even and included an odd prime factor \( p \), then \( p-1 \) would be even and could not evenly divide \( n-1 \), which is odd. As a result, to satisfy Korselt’s condition, every Carmichael number must be odd.
• Carmichael Numbers and Mersenne Numbers
  There is an intriguing, though largely coincidental, link between Carmichael numbers and Mersenne primes (numbers of the form \( 2^p - 1 \)). While no strict mathematical relationship exists, some Carmichael numbers include prime factors that also appear in the factorization of certain Mersenne numbers.

  Note: This is a sporadic phenomenon rather than a systematic connection. Mathematically, Carmichael and Mersenne numbers belong to entirely different realms. Carmichael numbers are composites that deceptively pass Fermat’s primality test, while Mersenne numbers are candidates for primality but do not always meet the criteria.

• Carmichael numbers must have at least three prime factors
  A Carmichael number cannot be made up of just two prime factors—it must have at least three.

  Proof. Suppose, for the sake of contradiction, that \( n \) is a Carmichael number with exactly two distinct prime factors, \( p \) and \( q \), meaning \( n = p \cdot q \), where \( p \) and \( q \) are distinct primes. By definition, since \( n \) is a Carmichael number, both \( p-1 \) and \( q-1 \) must divide \( n-1 \): $$ p - 1 \mid n - 1 $$ $$ q - 1 \mid n - 1 $$ Since they are divisors, the quotients \( \frac{n-1}{p-1} \) and \( \frac{n-1}{q-1} \) must be integers, meaning: \[ n - 1 \equiv 0 \pmod{p - 1} \] \[ n - 1 \equiv 0 \pmod{q - 1} \] We can also rewrite \( n - 1 \) by adding and subtracting \( p \): \[ n - 1 = p \cdot q - 1 \] \[ n-1 = p \cdot q - 1 + p - p \] \[ n-1 = p(q - 1) + (p - 1) \] Since we know that \[ n - 1 \equiv 0 \pmod{q - 1} \] substituting \( n-1 \) gives: \[ p(q - 1) + (p - 1) \equiv 0 \pmod{q - 1} \] Because \( q - 1 \) is divisible by itself, the remainder is zero, so we can simplify: \[ p - 1 \equiv 0 \pmod{q - 1} \] This tells us that \( q - 1 \) is a divisor of \( p - 1 \), meaning \( p - 1 \) is a multiple of \( q - 1 \): \[ p - 1 \text{ is a multiple of } q - 1, \quad \text{so } p - 1 \geq q - 1 \] Swapping \( p \) and \( q \) and repeating the argument, we get: \[ n - 1 = p \cdot q - 1 \] \[ n-1 = p \cdot q - 1 + q - q \] \[ n-1 = q(p - 1) + (q - 1) \] Since we also know that \[ n - 1 \equiv 0 \pmod{p - 1} \] it follows that: \[ q(p - 1) + (q - 1) \equiv 0 \pmod{p - 1} \] \[ (q - 1) \equiv 0 \pmod{p - 1} \] which tells us that \( p - 1 \) is a divisor of \( q - 1 \), meaning \( q - 1 \) must be a multiple of \( p - 1 \): \[ q - 1 \text{ is a multiple of } p - 1, \quad \text{so } q - 1 \geq p - 1 \] Since we have both \( p - 1 \geq q - 1 \) and \( q - 1 \geq p - 1 \), it follows that: \[ p - 1 = q - 1 \] which implies: \[ p = q \] But this contradicts our assumption that \( p \) and \( q \) are distinct primes. Therefore, the assumption that a Carmichael number can have exactly two prime factors leads to a contradiction. We conclude that a Carmichael number must have at least three distinct prime factors.

And so on.