Lembre da notação $\Z_p^*=\Z_p\setminus\{\overline 0\}$ ($p$ é primo).
No resto da página $p$ é um primo com $p\geq 3$.
\begin{array}{|c||c|c|c|c|c|c|}
\hline
\overline a & \overline 1 & \overline 2 & \overline 3& \overline 4& \overline 5 & \overline 6 \\\hline
\overline a^3 & \overline 1 & \overline 1 & \overline{-1}& \overline 1& \overline {-1} & \overline {-1} \\\hline
\end{array}
Observamos duas coisas:
- Se $\overline a\in\Z_7^*$ é quadrado, então $\overline a^3=\overline 1$.
- Se $\overline a\in\Z_7^*$ não é quadrado, então $\overline a^3=\overline{-1}$.
No lema seguinte demonstramos que as observações feitas no exemplo anterior não são coincidências.
\[
\psi:\Z_p^*\to\Z_p^*,\quad \overline a\mapsto \overline a^{2}.
\]
Temos que a imagem de $\psi$ é precisamente o conjunto dos quadrados em $\Z_p^*$. Além disso, assuma que $\overline a,\overline b\in\Z_p^*$ tais que $\psi(\overline a)=\psi(\overline b)$; ou seja $\overline a^2=\overline b^2$. A última equação é equivalente ao fato que $p\mid a^2-b^2=(a-b)(a+b)$ implicando que $p\mid a-b$ ou $p\mid a+b$ e assim
\[
b\equiv \pm a\pmod p\quad\mbox{e}\quad \overline b=\pm\overline a.
\]
Além disso, $\overline a$ e $\overline{-a}$ são distintos, pois se $\overline a=\overline{-a}$, então $\overline 2\overline a=\overline 0$ que implica (como $\overline 2$ é invertível) que $\overline a=0$ que não é o caso, pois $\overline a\in\Z_p^*$.
Portanto cada elemento $\overline b$ na imagem de $\psi$ existem precisamente dois elementos $\overline a$ e $-\overline a$ tal que $\psi(\overline a)=\psi(-\overline a)=\overline b$. Como $|\Z_p^*|=p-1$ a imagem de $\psi$ contém $(p-1)/2$ elementos e assim há $(p-1)/2$ quadrados em $\Z_p^*$.
Assuma que $\overline a\in\Z_p^*$ é um quadrado. Seja $\overline b\in\Z_p^*$ tal que $\overline a=\overline b^2$. O Pequeno Teorema de Fermat implica que
\[
\overline a^{(p-1)/2}=(\overline b^2)^{(p-1)/2}=\overline b^{p-1}=\overline 1.
\]
Agora assuma que $\overline a\in\Z_p^*$ não é um quadrado. Defina
\[
\vartheta:\Z_p^*\to\Z_p^*,\quad \overline b\mapsto \overline a/\overline b=\overline a\overline b^{-1}.
\]
Note que $\vartheta$ é uma bijeção e que $\vartheta(\overline b)=\overline c$ se e somente se $\vartheta(\overline c)=\overline b$. Além disso $\overline b\vartheta(\overline b)=\overline a$ para todo $\overline b\in\Z_p^*$ e o fato que $\overline a$ não é quadrado implica que $\vartheta(\overline b)\neq\overline b$ para todo $\overline b\in\Z_p^*$.
Vamos enumerar os elementos de $\Z_p^*$ como
\[
\Z_p^*=\{\overline b_1,\vartheta(\overline b_1),\overline b_2,\vartheta(\overline b_2),\ldots,\overline b_
{(p-1)/2},\vartheta(\overline b_{(p-1)/2})\}.
\]
Ora, o Teorema de Wilson nos diz que
\[
-1\equiv (p-1)!\equiv 1\cdot 2\cdots (p-1)\pmod p
\]
e isso implica que
\begin{align*}
\overline{-1}&= \overline 1\cdot \overline 2\cdots \overline{p-1}\\&=(\overline b_1\vartheta(\overline b_1))(\overline b_2\vartheta(\overline b_2))\cdots(\overline b_{(p-1)/2}\vartheta(\overline b_{(p-1)/2}))\\&=\overline a^{(p-1)/2}.
\end{align*}
É imediato da definição que $a$ é resíduo quadrático módulo $p$ se e somente se $\overline a$ é um quadrado em $\Z_p$.
\[
a\equiv 1,2,4\pmod 7
\]
enquanto $a$ é resíduo não quadrático se e somente se
\[
a\equiv 3,5,6\pmod 7.
\]
Se $a\equiv 0\pmod 7$, então o conceito não é definido para $a$.
\[
\left(\frac ap\right)=\left\{\begin{array}{ll} 1 & \mbox{se $a$ é resíduo quadrático módulo $p$;}\\
-1& \mbox{se $a$ é resíduo não quadrático módulo $p$;}\\
0 & \mbox{se $p\mid a$}.\end{array}\right.
\]
\[
\left(\frac a7\right)=\left\{\begin{array}{ll} 1 & \mbox{se $a\equiv 1,2,4\pmod 7$;}\\
-1& \mbox{se $a\equiv 3,5,6\pmod 7$;}\\
0 & \mbox{se $a\equiv 0\pmod 7$.}\end{array}\right.
\]
\[
\left(\frac ap\right)\equiv a^{(p-1)/2} \pmod p.
\]
O seguinte teorema famoso é conhecido como a Lei da Reciprocidade Quadrática. Este teorema será apresentado sem demonstração.
\[
\left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}2\frac{q-1}2}
\]
Para saber mais detalhes sobre o assunto, assista o vídeo no canal Mathologer.