31.8 Primality testing

31.8-1

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.8-2 $\star$

It is possible to strengthen Euler's theorem slightly to the form

$a^{\lambda(n)} \equiv 1 (\mod 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\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 "square-free" (not divisible by the square of any prime) and the product of at least three primes. (For this reason, they are not very common.)

(Omit!)

31.8-3

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 & (\mod n), \\ x^2 - 1 & \equiv & 0 & (\mod n), \\ (x + 1)(x - 1) & \equiv & 0 & (\mod n). \end{array} $$

$n \mid (x + 1)(x - 1)$, suppose $\gcd(x - 1, n) = 1$, then $n \mid (x + 1)$, then $x \equiv -1 (\mod 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$.