Exercise 3.2.15* (Pépin's test)

Proof. Let $q=4^n+1$ where $n$ is a positive integer. Then $q\equiv 1(\mathit{mod}4)$.

Suppose that $q$ is a prime number. By the law of quadratic reciprocity and Theorem 3.1,

Therefore, using Theorem 3.1(1),

Conversely, assume $3^{(q-1)∕2}\equiv -1(\mathit{mod}q)$. Then $3^{2^{2n-1}}\equiv -1(\mathit{mod}q)$, and $3^{2^{2n}}={\left(3^{2^{2n-1}}\right)}^2\equiv 1(\mathit{mod}q)$. This shows that the order $d$ of $3$ modulo $q$ satisfies

hence $d=2^{2n}=4^n=q-1$.

Therefore no two elements among the integers $\{1,3^1,3^2,\dots ,3^{q-2}\}$ are congruent modulo $q$. Consider the set $S=\{{[1]}_q,{[3]}_q,{[3]}_q^2\dots ,{[3]}_q^{q-2}\}\subseteq {(\mathbb{Z}∕\mathit{q\mathbb{Z}})}^{\text{∗}}$. Then $|S|=q-1$, and $S\subset {(\mathbb{Z}∕\mathit{q\mathbb{Z}})}^{\text{∗}}$, where $|{(\mathbb{Z}∕\mathit{q\mathbb{Z}})}^{\text{∗}}|=q-1=|S|$, thus ${(\mathbb{Z}∕\mathit{q\mathbb{Z}})}^{\text{∗}}=S$. Every element of ${(\mathbb{Z}∕\mathit{q\mathbb{Z}})}^{\text{∗}}$ is invertible (because ${[3]}_q$ is invertible, so ${[3]}_q^j$ is invertible for all $j\ge 0$). This shows that $\mathbb{Z}∕\mathit{q\mathbb{Z}}$ is a field. Therefore $q$ is a prime number (and $3$ is a primitive root modulo $q$). □