31.8 Primality testing
31.81¶
Prove that if an odd integer $n > 1$ is not a prime or a prime power, then there exists a nontrivial square root of $1$ modulo $n$.
(Omit!)
31.82 $\star$¶
It is possible to strengthen Euler's theorem slightly to the form
$a^{\lambda(n)} \equiv 1 \pmod n$ for all $a \in \mathbb Z_n^*$,
where $n = p_1^{e_1} \cdots p_r^{e_r}$ and $\lambda(n)$ is defined by
$$\lambda(n) = \text{lcm}(\phi(p_1^{e_1}), \ldots, \phi(p_r^{e_r})). \tag{31.42}$$
Prove that $\lambda(n) \mid \phi(n)$. A composite number $n$ is a Carmichael number if $\lambda(n) \mid n  1$. The smallest Carmichael number is $561 = 3 \cdot 11 \cdot 17$; here, $\lambda(n) = \text{lcm}(2, 10, 16) = 80$, which divides $560$. Prove that Carmichael numbers must be both "squarefree" (not divisible by the square of any prime) and the product of at least three primes. (For this reason, they are not very common.)

Prove that $\lambda(n) \mid \phi(n)$.
We have
$$ \begin{aligned} n & = p_1^{e_1} \cdots p_r^{e_r} \\ \phi(n) & = \phi(p_1^{e_1}) \times \dots \times \phi(p_r^{e_r}). \end{aligned} $$
Thus,
$$ \begin{aligned} \lambda(n) & \mid \phi(n) \\ \Rightarrow \text{lcm}(\phi(p_1^{e_1}, \ldots, \phi(p_r^{e_r})) & \mid (\phi(p_1^{e_1}) \times \dots \times \phi(p_r^{e_r})) \end{aligned} $$

Prove that Carmichael numbers must be "squarefree" (not divisible by the square of any prime).
Assume $n = p^\alpha m$ is a Carmichael number, where $\alpha \ge 2$ and $p \nmid m$.
By the Chinese Remainder Theorem, the system of congruences
$$ \begin{aligned} x & \equiv 1 + p \pmod p^\alpha, \\ x & \equiv 1 \pmod m \end{aligned} $$
has a solution $a$. Note that $\gcd(a, n) = 1$.
Since $n$ is a Carmichael number, we have $a^{n  1} \equiv 1 \pmod n$. In particular, $a^{n  1} \equiv 1 \pmod {p^\alpha}$; therefore, $a^n \equiv a \pmod {p^2}$.
So, $(1 + p)^n \equiv 1 + p \pmod {p^2}$. Expand $(1 + p)^n$ modulo $p^2$ using the binomial theorem. We have
$$(1 + p)^n \equiv 1 \pmod {p^2},$$
since the first two terms of the expansion are $1$ and $np$, and the rest of the terms are divisible by $p^2$.
Thus, $1 \equiv 1 + p \pmod {p^2}$. This is impossible.

Prove that Carmichael numbers must be the product of at least three primes.
Assume that $n = pq$ is a Carmichael number, where $p$ and $q$ are distant primes and $p < q$.
Then we have
$$ \begin{aligned} & q \equiv 1 \pmod{q  1} \\ \Rightarrow & n \equiv pq \equiv p \pmod{q  1} \\ \Rightarrow & n  1 \equiv p  1 \pmod{q  1}, \end{aligned} $$
Here, $0 < p − 1 < q − 1$ , so $n − 1$ is not divisible by $q − 1$.
31.83¶
Prove that if $x$ is a nontrivial square root of $1$, modulo $n$, then $\gcd(x  1, n)$ and $\gcd(x + 1, n)$ are both nontrivial divisors of $n$.
$$ \begin{array}{rlll} x^2 & \equiv & 1 & \pmod n, \\ x^2  1 & \equiv & 0 & \pmod n, \\ (x + 1)(x  1) & \equiv & 0 & \pmod n. \end{array} $$
$n \mid (x + 1)(x  1)$, suppose $\gcd(x  1, n) = 1$, then $n \mid (x + 1)$, then $x \equiv 1 \pmod n$ which is trivial, it contradicts the fact that $x$ is nontrivial, therefore $\gcd(x  1, n) \ne 1$, $\gcd(x + 1, n) \ne 1$.