A lei da reciprocidade quadrática

A lei de Gauss de reciprocidade quadrática afirma que se p e q são primos há uma relação direta entre p ser quadrado módulo qe q ser quadrado módulo p. Este teorema fornece um rápido algoritmo para determinar se a é quadrado módulo p onde a é um inteiro e p um número primo.

Definição 2.16: Seja p um primo e a um inteiro. Definimos o símbolo de Lagrange $(\frac{a}{p})$ por

$$\left(\frac{a}{p}\right) = \begin{cases} 0& \text{se $p$\spac... ...mid a$\space e $a$\space é quadrado módulo $p$ }. \end{cases}$$

Proposição 2.17: Seja p um primo ímpar e $a \in {\mathbb{Z} }$ tal que $p \nmid a$. Então $\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p$.

Dem: Sabemos que se $p \nmid a$ então $a^{p-1} \equiv 1 \pmod p$, ou seja, X^p-1-1 tem como raízes $1,2,\dots,p-1$ em ${\mathbb{Z} }/(p)$. Por outro lado, $X^{p-1}-1 = ({X^{\frac{p-1}{2}}-1})(X^{\frac{p-1}{2}} + 1)$. Se existe $b \in {\mathbb{Z} }$ tal que $a \equiv b^2 \pmod p$ então $a^{\frac{-1}{2}} \equiv b^{p-1} \equiv 1 \pmod p$; ou seja, $\left(\frac{a}{p}\right) = 1 \equiv a^{\frac{p-1}{2}} \pmod p$. Como $X^2 \equiv Y^2 \pmod p \Leftrightarrow X \equiv \pm Y \pmod p$, há pelo menos $\frac{p-1}{2}$ quadrados em $({\mathbb{Z} }/(p))^*$, logo os quadrados são exatamente as raízes de $X^{\frac{p-1}{2}} - 1$ em ${\mathbb{Z} }/(p)$, donde os não quadrados são exatamente as raízes de $X^{\frac{p-1}{2}} + 1$, ou seja, se $(\frac bp)=-1$ então $b^{\frac{p-1}{2}} \equiv -1 \pmod p$.          $\blacksquare$

Corolário 2.18: Se p é primo ímpar então $(\frac{-1}{p}) = (-1)^{\frac{p-1}{2}}$.

Vamos agora reinterpretar a Proposição 1. Seja $a \in ({\mathbb{Z} }/(p))^\ast$. Para cada $j = 1,2,\ldots,\frac{p-1}{2}$ escrevemos $a \cdot j$ como $\varepsilon_j m_j$ com $\varepsilon_j \in \{-1,1\}$ e $m_j \in \{1,2,\dots,\frac{p-1}{2}\}$. Se $m_i \ne m_j$ temos $a \cdot i = a \cdot j$ ou $a \cdot i = - a \cdot j$; a primeira possibilidade implica i = j e a segunda é impossível. Assim, se $i \ne j$ temos $m_i \ne m_j$ donde $\{m_1,m_2,\dots,m_{\frac{p-1}{2}}\} = \{1,2,\dots,\frac{p-1}{2}\}$. Assim
$$\begin{align}\left(\frac{a}{p}\right) &\equiv a^{\frac{p-1}{2}} \notag\\ &= \fr... ...arepsilon_1 \varepsilon_2 \cdots \varepsilon_{\frac{p-1}{2}} \pmod p \end{align}$$
donde $(\frac ap) = \varepsilon_1\varepsilon_2\dots\varepsilon_{\frac{p-1}{2}}$, pois ambos pertencem a $\{-1,1\}$. Assim, $(\frac ap) = (-1)^m$ onde m é o número de elementos j de $\{1,2,\ldots,\frac{p-1}{2}\}$ tais que $\varepsilon_j=-1$. Como primeira conseqüência deste fato temos o seguinte resultado.

Proposição 2.19: Se p é um primo ímpar então

$$(\frac{2}{p}) = (-1)^{\frac{p^2-1}{8}} = \begin{cases} 1, & \... ...\pmod 8,\\ -1, & \text{se }p \equiv \pm 3 \pmod 8. \end{cases}$$

Dem: Se $p\equiv 1 \pmod 4$, digamos p=4k+1, temos $\frac{p-1}{2} = 2k$. Como $1 \le 2j \le \frac{p-1}{2}$ para $j \le k$ e $\frac{p-1}{2} < 2j \le p-1$ para $k+1 \le j \le 2k$, temos

$$(\frac ap) = (-1)^k = \begin{cases} 1, &\text{se }p \equiv 1 \pmod 8,\\ -1, &\text{se }p \equiv 5 \pmod 8. \end{cases}$$

Se $p\equiv 3 \pmod 4$, digamos p = 4k+3, temos $\frac{p-1}{2} = 2k+1$. Para $1 \le j \le k$ temos $1 \le 2j \le \frac{p-1}{2}$ e para $k+1 \le j \le 2k+1$ temos $\frac{p-1}{2} < 2j \le p-1$, donde

$$(\frac ap) = (-1)^{k+1} = \begin{cases} -1, &\text{se }p \equiv 3 \pmod 8,\\ 1, &\text{se }p \equiv 7 \pmod 8. \end{cases}$$

         $\blacksquare$

Teorema 2.20: (Lei de reciprocidade quadrática) Sejam p e q primos ímpares. Então $(\frac pq) = (-1)^{(p-1)(q-1)/4} (\frac qp)$.

Dem: Na notação acima, com a=q, para cada $j \in P$, onde

$$P = \{ 1, 2, \ldots, (p-1)/2 \},$$

temos que $\varepsilon_j=-1$ se e só se existe $y \in {\mathbb{Z} }$ tal que $-(p-1)/2 \le qj - py < 0$. Tal y deve pertencer a Q, onde

$$Q = \{ 1, 2, \ldots, (q-1)/2 \}.$$

Assim, temos que $(\frac qp) = (-1)^m$ onde m = |X| e

$$X = \left\{(x,y) \in P \times Q \mid -(p-1)/2 \le qx - py < 0 \right\};$$

note que qx - py nunca assume o valor 0. Analogamente, $(\frac pq) = (-1)^n$, onde n = |Y| e

$$Y = \left\{(x,y) \in P \times Q \mid 0 < qx - py \le (q-1)/2 \right\}.$$

Daí segue que $(\frac pq)(\frac qp) = (-1)^k$ onde k = m+n = |Z| onde

$$Z = \left\{(x,y) \in P \times Q \mid -(p-1)/2 \le qx - py \le (q-1)/2 \right\}$$

pois qx - py nunca assume o valor 0. Temos k = |C| - |A| - |B| onde $C = P \times Q$,
$$\begin{align}A &= \{(x,y) \in C \mid qx-py < -(p-1)/2 \}, \notag\\ B &= \{(x,y) \in C \mid qx-py > (q-1)/2 \}. \notag \end{align}$$
Como |C| = (p-1)(q-1)/4, basta mostrar que |A| = |B|. Mas $f: C \to C$ definida por f(x,y) = (((p+1)/2) - x, ((q+1)/2) - y)define uma bijeção entre A e B.          $\blacksquare$