Exercise 3.1.3 (Lemma of Gauss)

Proof.

• If $p=7$, then $(p-1)∕2=3$, and

  $i$	1	2	3
  $3^i\mathit{mod}7$	3	2	6

  If $n$ is the number of these residues that exceed $p∕2$, then $n=1$. The Lemma of Gauss (Theorem 3.2) gives

  $$\left(\frac{3}{7}\right)={(-1)}^n=-1.$$

  Therefore $3$ is quadratic nonresidue of $7$.

• If $p=13$, then $(p-1)∕2=6$, and

  $i$	1	2	3	4	5	6
  $3^i\mathit{mod}7$	3	9	1	3	9	1

  Then $n=2$, thus

  $$\left(\frac{3}{13}\right)={(-1)}^n=1.$$

  Therefore $3$ is a quadratic residue of $13$.