Exercise 3.1.12 (Product of residues and non residues)

Question

Denote quadratic residue by $r$, nonresidues by $n$. Prove that $r_1r_2$ and $n_1n_2$ are residues and that $r n$ is a nonresidue for any odd prime $p$. Give a numerical example to show that the product of two nonresidues is not necessarily a quadratic residue modulo $12$.

Richard Ganaye · Accepted Answer

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof} Let $r, r_1, r_2$ be residues, and $n, n_1,n_2$ be nonresidues modulo $p$. Then
\begin{align*}
\legendre{r_1r_2}{p} &= \legendre{r_1}{p}\legendre{r_2}{p} = 1 \cdot 1= 1,\
\legendre{n_1n_2}{p} &= \legendre{n_1}{p}\legendre{n_2}{p} = (-1) \cdot(-1) = 1,\
\legendre{r n }{p} &= \legendre{r}{p}\legendre{n}{p} =1 \cdot(-1) = -1,\
\end{align*}
thus $r_1r_2 , n_1n_2$ are residues, and $rn$ is a non residue modulo $p$.

The product of two residues, or two nonresidues, is a residue modulo $p$.

The product of a residue and a nonresidue is a non residue modulo $p$.

\bigskip
This is false if we replace $p$ by a composite number. To give a counterexample, take $m = 12$. By Definition 3.1, $a$ is a quadratic residue modulo $12$ if $a \wedge 12 = 1$ and $x^2 \equiv a \pmod {12} = 1$ has a solution. The condition $a \wedge 12 = 1$  implies $a\equiv  \pm 1, \pm 5 \pmod{12}$, but $(\pm5)^2 \equiv 1 \pmod {12}$, therefore $1$ is the only quadratic residue modulo $12$, and $5,7$ are non residues. But $5 \cdot 7 = 35 \equiv -1 \pmod {12}$ is a non residue modulo $12$. The product of two nonresidues is not necessarily a quadratic residue modulo $12$.
\end{proof}

Exercise 3.1.12 (Product of residues and non residues)

Answers

Comments

Exercise 3.1.12 (Product of residues and non residues)

Answers

Comments

Add answer