Why is $ 561 = 3*11*17 $ the smallest Carmichael number?

A composite integer n is a Carmichael number if the only Fermat witnesses for $n$ are those $a \in \mathbb Z_n^+$ which are not coprime with $n$. The smallest example of such a number is $561 = 3 · 11 · 17$

I think I understand the definition, but I don't quite understand why is the smallest Carmichael number is the above mentioned number. Please clarify.

Solution 1:

First, a Carmichael number cannot be even. If $n$ is an even composite, then $(n-1)^{n-1} \equiv (n-1) \pmod n$, and since $n > 2$, $n-1 \not\equiv 1 \pmod n$ (and $n-1$ and $n$ are coprime).

Next, a Carmichael number must be squarefree. To see that, suppose $n = p^k\cdot m$ with $k > 1$ and $p \not\mid m$. If $a^e \equiv 1 \pmod n$, then also $a^e \equiv 1 \pmod{p^k}$, since $p^k \mid n$.

Now consider $a = 1 + m\cdot p^{k-1}$. All prime divisors of $n$ divide either $m$ or $p^{k-1}$, hence $a$ is coprime to $n$. But

$$a^e = \sum_{j = 0}^e \binom{e}{j} 1^{e-j}m^jp^{j(k-1)} \equiv 1 + e\cdot m\cdot p^{k-1} \pmod {p^k},$$

and since $p \not\mid m$, we find $a^e \equiv 1 \pmod {p^k} \iff p \mid e$. Since $p$ divides $n$,it doesn't divide $n-1$, hence $a^{n-1} \not\equiv 1 \pmod{p^k}$, so also $a^{n-1} \not\equiv 1 \pmod{n}$. (Of course, one could also just cite the theorem that $\mathbb{Z}_{p^k}^\times$ is cyclic for odd primes $p$ to conclude that Carmichael numbers must be squarefree.)

So, a Carmichael number must be odd and squarefree. Let $n = p\cdot m$ be a Carmichael number with $p$ an odd prime. Since $\mathbb{Z}_p^\times$, the group of units (nonzero elements) in the field $\mathbb{Z}_p$, is cyclic - every finite multiplicative subgroup of a field is cyclic - there are $a$ such that $a^e \equiv 1 \pmod p \iff (p-1)\mid e$, hence a necessary condition for Carmichael numbers is that $(p-1) \mid (n-1)$ for all primes $p\mid n$. This condition is also sufficient, because then $a^{n-1} = \bigl(a^{p-1}\bigr)^r \equiv 1^r \equiv 1 \pmod p$ for all $a$ coprime to $n$ and $p\mid n$, so $a^{n-1} \equiv 1 \pmod n$ for all $a$ coprime to $n$.

Now, $n-1 = p\cdot m-1 = (p-1)\cdot m + (m-1)$, and $(p-1) \mid (n-1) \iff (p-1) \mid (m-1)$, from which follows that $p < m$ (equality is ruled out by squarefreeness here), in particular, all prime divisors of a Carmichael number $n$ are smaller than $\sqrt{n}$, hence a Carmichael number has at least three (distinct) prime divisors.

Let's try to find a few Carmichael numbers with three prime factors.

Suppose the smallest prime factor is $3$. Then $(3-1) \mid (n-1)$, and the divisibility condition is satisfied for $3$. Let $p < q$ be the other two prime factors. Then $(p-1) \mid (3q-1)$ and $(q-1) \mid (3p-1)$ are necessary (and sufficient) conditions for $3pq$ to be a Carmichael number. Since $p < q$, we have $s = \dfrac{3p-1}{q-1} < 3$. $s = 1$ is impossible, since $3p$ isn't prime, so we must have $s = 2$, or $q = \dfrac{3p+1}{2}$. That implies $p \equiv 3 \pmod 4$, otherwise $\frac{3p+1}{2}$ is even. Further, $3q-1 = \frac{9p+1}{2}$ must be a multiple of $p-1$. Now, $4(p-1) < \frac{9p+1}{2} < 6(p-1)$ (the latter because $p \geqslant 5$), so the only possibility is $5(p-1) = \frac{9p+1}{2} \iff p = 11$. Then $q = \frac{3p+1}{2} = 17$, and we check that indeed $(11-1)\mid(3\cdot 17-1)$ and $(17-1)\mid(3\cdot 11-1)$, so the only Carmichael number that is a product of three primes and is divisible by $3$ is $561 = 3\cdot 11 \cdot 17$.

Suppose next that $n = 5\cdot p \cdot q$ with $5 < p < q$. First, we note that the condition $(5-1)\mid (pq-1)$ implies that $p \equiv q \pmod 4$. Then, like above, $1 < s = \frac{5p-1}{q-1} < 5$.

If $s = 2$, we have $q = \frac{5p+1}{2}$, and plugging that into $(p-1)\mid (5q-1)$ yields $(p-1) \mid \frac{25p+3}{2}$. Since $p \geqslant 7$, it follows that $12 < r = \frac{25p+3}{2(p-1)} < 16$. Only $r = 13$ leads to an integer quotient, and $p = 29,\, q = 73$, for the Carmichael number $5\cdot 29 \cdot 73 = 10585$.

If $s = 3$, we obtain $q = \frac{5p+2}{3}$ and need to have $r = \frac{25p+7}{3(p-1)} > 8$ an integer. $p \geqslant 7$ implies $r < 11$, and $r = 9$ leads to $p = 17,\, q = 29$ and the Carmichael number $5\cdot 17 \cdot 29 = 2465$. $r = 10$ leads to nothing.

If $s = 4$, we obtain $q = \frac{5p+3}{4}$ and need $r = \frac{25p+11}{4(p-1)} > 6$ integral. $p \geqslant 7$ implies $r < 8$, hence $r =7$ is the only possibility and leads to $p = 13,\, q = 17$ and the Carmichael number $5\cdot 13 \cdot 17 = 1105$.

$7\cdot 11 \cdot 13 = 1001 > 561$, so a Carmichael number with three prime divisors whose smallest prime factor is $\geqslant 7$ cannot be the smallest Carmichael number.

The smallest squarefree odd number with four prime divisors is $3\cdot 5 \cdot 7 \cdot 11 = 1155$, which is larger than $561 = 3\cdot 11 \cdot 17$.

So we have now verified that $561$ is indeed the smallest Carmichael number.