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 \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 "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.)

  1. 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} $$

  2. Prove that Carmichael numbers must be "square-free" (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.

    Stack Exchange Reference

  3. 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$.

    Stack Exchange Reference

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 & \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$.