Exercise 3.1.11 (There are equally many residues and non residues for an odd prime)

Question

Let $g$ be a primitive root of an odd prime $p$. Prove that the quadratic residues modulo $p$ are congruent to $g^2, g^4, g^6,\ldots,g^{p-1}$ and that the non residues are congruent to $g, g^3,\ldots,g^{p-2}$. Thus there are equally many residues and non residues for an odd prime.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

\begin{proof}

{\bf First proof.} 
 
 Let $g$ be a primitive root of an odd prime $p$. Then every integer $x$ such that $p 
mid x$ satisfies $x = g^j$ for some $j \in [\![1,p-1]\!]$ (where $g^{p-1} = 1$).
\begin{itemize}
\item If $j$ is even, then $j = 2k$ for some integer $k$, and $x \equiv (g^k)^2 \pmod p$ is a quadratic residue.

\item If $j$ is odd, then $j = 2k+1$. Assume for contradiction that $x$ is a quadratic residue. Then $g^{2k+1} \equiv x \equiv a^2 \pmod p$, where $a \in \Z$. If $\overline{g}\  (= g^{p-2})$ is an inverse of $g$ modulo $p$, i.e. $g \overline{g} \equiv 1 \pmod p$, then $g \equiv (a \overline{g}^k)^2 =b^2 \pmod p$, where $b = a \overline{g}^k$. But then $g^{(p-1)/2} = b^{p-1} \equiv 1 \pmod p$, thus the order of $g$ is at most $(p-1)/2$. Since $g$ is a generator, this is a contradiction. Therefore $x = g^{2k+1}$ is a quadratic nonresidue.
\end{itemize}

This shows that the quadratic residues modulo $p$ are congruent to $g^2, g^4, g^6,\ldots,g^{p-1}$, and that the non residues are congruent to  $g, g^3,\ldots,g^{p-2}$. Thus there are $(p-1)/2$ residues and $(p-1)/2$ non residues for an odd prime in $[\![1, p-1]\!]$.
\end{proof}

\bigskip
{\bf Second proof.} (without primitive element)

Let $\F_p = \Z/p\Z$ the field with $p$ elements, so that $\F_p^*$ is an abelian group. Consider the map
$$\varphi 
\left\{
\begin{array}{ccl}
\F_p^* & 	o &\F_p^*\
x & \mapsto &x^2.
\end{array}
ight.
$$
Then $\varphi$ is a group homomorphism. By the first isomorphism theorem, 
$$\mathrm{im}\ \varphi \simeq \F_p^*/ \ker \varphi.$$
Moreover, since $\F_p$ is a field,
$$x \in \ker(\varphi) \iff x^2 = 1 \iff (x-1)(x+1) = 0 \iff x \in \{-1,1\},$$
therefore
$$\ker \varphi = \{-1,1\}.$$
This shows that
$$|\mathrm{im}\  \varphi| = |\F_p^* |/ 2 = (p-1)/2.$$
Here $\mathrm{im}\  \varphi$ is the subgroup of squares in $\F_p^*$. We have proved that there are as many squares as non squares in $\F_p^*$. In other words, there are equally many residues and non residues for an odd prime  in $[\![1, p-1]\!]$.

\bigskip
{\bf Third proof} (See Ireland , Rosen)

The squares in $\F_p^*$ are the roots of the polynomial $x^{(p-1)/2} - 1 \in \F_p[x]$, which has at most $(p-1)/2$ roots, because $\F_p$ is a field. Since $x^{p-1} - 1$ has $p$ roots (all the elements of $\F_p^*$), and
$$x^{p-1} - 1 = (x^{\frac{p-1}{2}}- 1)(x^{\frac{p-1}{2}} + 1),$$
it is impossible that $x^{(p-1)/2} - 1 $ has less than $(p-1)/2$ roots, otherwise $x^{p-1} - 1$ would have less that $p-1$ roots, which is false. Therefore $x^{\frac{p-1}{2}}- 1$ has $(p-1)/2$ roots, so $\F_p^*$ contains exactly $(p-1)/2$ squares. There are as many squares as non squares in $\F_p^*$.

Exercise 3.1.11 (There are equally many residues and non residues for an odd prime)

Answers

Comments

Exercise 3.1.11 (There are equally many residues and non residues for an odd prime)

Answers

Comments

Add answer