Exercise 3.3.13* (Characterization of the the set of quadratic residues)

Question

Let the integers $1,2,\cdots,p-1$ modulo $p$, $p$ an odd prime, be divided into two nonempty sets $\mathscr{S}_1$ and $\mathscr{S}_2$, so that the product of two elements in the same set is in $\mathscr{S}_1$, whereas the product of an element of $\mathscr{S}_1$ and an element of $\mathscr{S}_2$ is in $\mathscr{S}_2$. Prove that $\mathscr{S}_1$ consists of the quadratic residues, $\mathscr{S}_2$ of the non residues, modulo $p$.

\bigskip
Hint. Use a primitive root modulo $p$.

Richard Ganaye · Accepted Answer

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

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

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

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

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

I don't use the hint, but some (easy) group theory.

\begin{proof}Let $\F_p$ be the field $\Z/p\Z$ with $p$ elements. By hypothesis, $\mathscr{S}_1 
e \varnothing, \mathscr{S}_2 
e \varnothing$, 
$$\mathscr{S}_1 \cup \mathscr{S}_2 = \F_p^*, \qquad \mathscr{S}_1 \cap \mathscr{S}_2 = \varnothing,$$
and, for all $x, y \in \F_p^*$,
\begin{align}
(a)\ \left\{
\begin{array}{l}
x \in \mathscr{S}_1\
y \in \mathscr{S}_1
\end{array}
ight.
\Rightarrow xy \in \mathscr{S}_1,
\qquad
(b)\ \left\{
\begin{array}{l}
x \in \mathscr{S}_2\
y \in \mathscr{S}_2
\end{array}
ight.
\Rightarrow xy \in \mathscr{S}_1,
\qquad
(c)\ \left\{
\begin{array}{l}
x \in \mathscr{S}_1\
y \in \mathscr{S}_2
\end{array}
ight.
\Rightarrow xy \in \mathscr{S}_2.
\end{align}

Write $\mathscr{C}$ the subgroup of squares in $\F_p^*$ (the classes modulo $p$ of quadratic residues):
$$\mathscr{C} = \{y \in \F_p^* \mid \exists x \in \F_p^*,\ y = x^2\} = \{x^2 \mid x \in \F_p^*\}.$$
Let 
$$\varphi 
\left\{
\begin{array}{ccl}
\F_p^* & 	o & \F_p^*\
x & \mapsto & x^2
\end{array}
ight.
$$
Then $\varphi$ is a group homomorphism, $\mathscr{C} = \mathrm{im}(\varphi)$, and $\ker(\varphi) =\{x \in \F_p^* \mid x^2 = 1\} = \{-1,1\}$. The first isomorphism theorem shows that
$$\mathscr{C} \simeq \F_p^*/\{-1,1\},$$
so that the order of $\mathscr{C}$ is $(p-1)/2$, and the index of $\mathscr{C}$ is
$$(\F_p^*: \mathscr{C}) = 2.$$
We want to show that $\mathscr{S}_1 = \mathscr{C}$. Every element $y \in \mathscr{C}$ is of the form $y = x \cdot x,\ x \in \F_p^*$. If $x \in \mathscr{S}_1$, then $y \in \mathscr{S}_1$ by (1.a), and if $x \in \mathscr{S}_2$, then $y \in \mathscr{S}_1$ by (1.b). In both cases $y \in \mathscr{S}_1$, therefore
$$\mathscr{C} \subseteq \mathscr{S}_1.$$

Since $\mathscr{S}_1$ is finite, the condition (1.a) shows that $\mathscr{S}_1 
e \varnothing$ is a subgroup of $\F_p^*$: if $x \in \mathscr{S}_1$, $x^{p-2} \in \mathscr{S}_1$, and $x\cdot x^{p-2} = x^{p-1} = 1$, so that $x^{-1} = x^{p-2} \in \mathscr{S}_1$.

Note that $ \mathscr{S}_1 \subsetneq \F_p^*$ : if $\mathscr{S}_1 = \F_p^*$, then $\mathscr{S}_2 = \varnothing$, which is false by hypothesis. So
$$\mathscr{C} \subseteq \mathscr{S}_1 \subsetneq \F_p^*.$$
Then 
$$2 = (\F_p^* : \mathscr{C}) = ( \F_p^* :  \mathscr{S}_1 ) (\mathscr{S}_1  : \mathscr{C}),$$
where  $( \F_p^* :  \mathscr{S}_1 ) >1$. This shows that $( \F_p^* :  \mathscr{S}_1 ) = 2$ and $(\mathscr{S}_1  : \mathscr{C}) = 1$, thus 
$$\mathscr{S}_1 = \mathscr{C}.$$
(and $\mathscr{S}_2 = \complement_{\F_p^*} \mathscr{S}_1 =  \complement_{\F_p^*} \mathscr{C}$.)

$\mathscr{S}_1$ consists of the group of squares of $(\Z/p\Z)^*$, $\mathscr{S}_2$ consists of the set of non squares.

\end{proof}

Exercise 3.3.13* (Characterization of the the set of quadratic residues)

Answers

Comments

Exercise 3.3.13* (Characterization of the the set of quadratic residues)

Answers

Comments

Add answer