Reciprocidad cuadrática y símbolo de Legendre

(i) Sea $a$ un RC: $a \equiv x^2 \pmod p$, así $a^{(p-1)/2} \equiv x^{p-1} \equiv 1 \pmod p$ por PTF.

Sea $a$ un NRC. Sabemos que $a^{(p-1)/2} \equiv \pm 1 \pmod p$ (pues es raíz de $t^2 - 1 = (t-1)(t+1)$ en el cuerpo $\mathbb F_p$). Si fuera $a^{(p-1)/2} \equiv 1$, entonces $a$ sería raíz de $x^{(p-1)/2} - 1$, que tiene a lo sumo $(p-1)/2$ raíces en $\mathbb F_p$. Pero los $(p-1)/2$ RC ya son $(p-1)/2$ raíces distintas de este polinomio (como vimos arriba). Así $a$ no puede ser raíz, contradicción. Luego $a^{(p-1)/2} \equiv -1 \pmod p$.

(iv) La función $x \mapsto x^2 \pmod p$ envía $\{1, \ldots, p-1\}$ a los RC. Como $x^2 \equiv (-x)^2 = (p-x)^2$, cada RC tiene exactamente dos preimágenes $\{x, p-x\}$. Hay $(p-1)/2$ pares, luego $(p-1)/2$ RC. Los restantes $(p-1)/2$ elementos son NRC. $\blacksquare$

(ii) Por el criterio de Euler: $\left(\frac{ab}{p}\right) \equiv (ab)^{(p-1)/2} = a^{(p-1)/2} b^{(p-1)/2} \equiv \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) \pmod p$. Como ambos lados están en $\{-1, 0, 1\}$ y son iguales módulo $p > 2$, son iguales. $\blacksquare$

Primera ley. Por el criterio de Euler: $\left(\frac{-1}{p}\right) \equiv (-1)^{(p-1)/2} \pmod p$. Como el valor es $\pm 1$, la igualdad se levanta a $\mathbb Z$. Finalmente, $(p-1)/2$ es par iff $p \equiv 1 \pmod 4$.

Segunda ley. Queremos saber si $2$ es RC módulo $p$. Consideramos el conjunto $\{1, 3, 5, \ldots, p-2\}$ (los $(p-1)/2$ impares en $\{1, \ldots, p-1\}$). Reducimos los productos $2 \cdot 1, 2 \cdot 3, 2 \cdot 5, \ldots, 2 \cdot \frac{p-1}{2}$ módulo $p$ al rango $[-(p-1)/2, (p-1)/2]$ y contamos cuántos quedan negativos. El número $\nu$ de negativos satisface $\left(\frac{2}{p}\right) = (-1)^\nu$ (por el Lema de Gauss, a continuación).

El análisis muestra que $\nu = (p^2 - 1)/8 \pmod 2$, lo que da la fórmula. $\blacksquare$

Utilizamos el Lema de Gauss y el método de conteo de Eisenstein.

Lema de Gauss. Sea $a$ coprimo con $p$. Consideramos los $\frac{p-1}{2}$ productos:

$a, 2a, 3a, \ldots, \frac{p-1}{2} \cdot a,$

reducidos a representantes en $\left\{-\frac{p-1}{2}, \ldots, -1, 1, \ldots, \frac{p-1}{2}\right\}$. Sea $\nu$ el número de representantes negativos. Entonces $\left(\frac{a}{p}\right) = (-1)^\nu$.

Demostración del Lema. Los representantes $r_1, \ldots, r_{(p-1)/2}$ son todos distintos en valor absoluto (porque si $|r_i| = |r_j|$, entonces $ia \equiv \pm ja \pmod p$, con $1 \leq i \leq j \leq (p-1)/2$; si el signo es $+$, $i = j$; si es $-$, $ia + ja \equiv 0$, $p \mid (i+j)a$, imposible pues $1 \leq i + j \leq p-1$). Así $\{|r_1|, \ldots, |r_{(p-1)/2}|\} = \{1, \ldots, (p-1)/2\}$.

Multiplicando: $a \cdot 2a \cdots \frac{p-1}{2}a = a^{(p-1)/2} \cdot \left(\frac{p-1}{2}\right)! \equiv (-1)^\nu \cdot \left(\frac{p-1}{2}\right)! \pmod p$ (el $(-1)^\nu$ proviene de cambiar el signo de los $\nu$ representantes negativos). Cancelando $\left(\frac{p-1}{2}\right)!$ (coprimo con $p$): $a^{(p-1)/2} \equiv (-1)^\nu \pmod p$. Por el criterio de Euler: $\left(\frac{a}{p}\right) = (-1)^\nu$. $\square$

Prueba de la reciprocidad (método de Eisenstein). Para $\left(\frac{q}{p}\right)$, aplicamos el Lema de Gauss: $\nu$ es el número de enteros en $\{q, 2q, \ldots, \frac{p-1}{2}q\}$ cuyo representante en $(-p/2, p/2)$ es negativo. Equivalentemente, $\nu$ es el número de $k \in \{1, \ldots, \frac{p-1}{2}\}$ tales que $kq \pmod p > p/2$, es decir, tales que $\lfloor 2kq/p \rfloor$ es impar.

Puede mostrarse (con un conteo cuidadoso sobre puntos del retículo) que:

$\nu \equiv \sum_{k=1}^{(p-1)/2} \left\lfloor \frac{kq}{p} \right\rfloor \pmod 2.$

La prueba de Eisenstein cuenta los puntos del retículo $\mathbb Z^2$ en el rectángulo $\{(x, y) : 1 \leq x \leq (p-1)/2,\; 1 \leq y \leq (q-1)/2\}$:

$\frac{p-1}{2} \cdot \frac{q-1}{2} \text{ puntos en total.}$

Cada punto está estrictamente por encima o por debajo de la diagonal $y = (q/p)x$ (nunca sobre ella, pues $p \nmid qx$ para $0 < x < p$). Los puntos bajo la diagonal son $\sum_{x=1}^{(p-1)/2} \lfloor qx/p \rfloor$, y los sobre la diagonal son $\sum_{y=1}^{(q-1)/2} \lfloor py/q \rfloor$.

Sumando:

$\sum_{x=1}^{(p-1)/2} \left\lfloor \frac{qx}{p} \right\rfloor + \sum_{y=1}^{(q-1)/2} \left\lfloor \frac{py}{q} \right\rfloor \;=\; \frac{p-1}{2} \cdot \frac{q-1}{2}.$

Pero $\left(\frac{q}{p}\right) = (-1)^{\sum \lfloor qx/p \rfloor}$ y $\left(\frac{p}{q}\right) = (-1)^{\sum \lfloor py/q \rfloor}$, así:

$\left(\frac{q}{p}\right) \cdot \left(\frac{p}{q}\right) \;=\; (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}. \qquad \blacksquare$