Lema de Gauss y reciprocidad cuadrática

Por qué necesitamos el Lema de Gauss

El criterio de Euler permite calcular $\left(\frac{a}{p}\right)$ elevando $a$ a la $(p-1)/2$-ésima potencia. Pero este cálculo, aunque correcto, no revela la estructura. El Lema de Gauss ofrece una interpretación combinatoria del símbolo que permite relacionar $\left(\frac{p}{q}\right)$ con $\left(\frac{q}{p}\right)$, algo que el criterio de Euler no hace directamente.

La idea central es reducir $a, 2a, 3a, \ldots, \frac{p-1}{2}a$ módulo $p$ al rango simétrico $\left(-\frac{p-1}{2}, \frac{p-1}{2}\right]$ y contar cuántos resultan negativos. Ese conteo determina el símbolo.

El Lema de Gauss

Sea $p$ primo impar y $p \nmid a$. Consideremos los $\frac{p-1}{2}$ múltiplos $a, 2a, 3a, \ldots, \frac{p-1}{2} \cdot a$. Reducimos cada uno módulo $p$ al representante en $\left\{-\frac{p-1}{2}, \ldots, -1, 1, 2, \ldots, \frac{p-1}{2}\right\}$ (el "rango simétrico centrado"). Sea $\nu$ el número de representantes negativos entre estos $\frac{p-1}{2}$ valores.

Lema de Gauss. $\left(\frac{a}{p}\right) = (-1)^\nu$.

Demostración. Los representantes en valor absoluto son una permutación de $\{1, 2, \ldots, \frac{p-1}{2}\}$: si dos múltiplos $ia$ y $ja$ tuvieran el mismo representante, ya sea $ia \equiv \pm ja \pmod{p}$, lo que daría $i \equiv \pm j \pmod{p}$, imposible para $1 \le i, j \le \frac{p-1}{2}$. Entonces multiplicando todos los representantes (con signo $(-1)^\nu$ extra por los negativos): $(-1)^\nu \cdot a^{(p-1)/2} \cdot \left(\frac{p-1}{2}\right)! \equiv \left(\frac{p-1}{2}\right)! \pmod{p}$. Cancelando el factorial: $(-1)^\nu \cdot a^{(p-1)/2} \equiv 1$, es decir $a^{(p-1)/2} \equiv (-1)^\nu$. Por el criterio de Euler, esto es $\left(\frac{a}{p}\right) \equiv (-1)^\nu$.

Cálculo de $\left(\frac{2}{p}\right)$

Aplicamos el Lema de Gauss con $a = 2$. Necesitamos contar cuántos de los valores $2, 4, 6, \ldots, p-1$ (los $\frac{p-1}{2}$ múltiplos de 2) tienen representante negativo en el rango simétrico. Un múltiplo $2k$ tiene representante negativo si y solo si $2k > \frac{p}{2}$, es decir $k > \frac{p}{4}$.

El número de enteros $k$ con $\frac{p}{4} < k \le \frac{p-1}{2}$ es $\nu = \frac{p-1}{2} - \left\lfloor \frac{p}{4} \right\rfloor$. Un cálculo por casos según $p \bmod 8$ muestra que $\nu$ es par si $p \equiv \pm 1 \pmod{8}$ e impar si $p \equiv \pm 3 \pmod{8}$.

En consecuencia: $2$ es residuo cuadrático módulo $p$ si y solo si $p \equiv \pm 1 \pmod{8}$.

Ejemplo: $p = 7 \equiv -1 \pmod 8$. Entonces $\left(\frac{2}{7}\right) = 1$. Verificamos: $3^2 = 9 \equiv 2 \pmod 7$. Correcto.

La Ley de Reciprocidad Cuadrática

El resultado más profundo de la teoría de residuos cuadráticos elementales es la siguiente ley, conjeturada por Euler y Legendre, y demostrada por primera vez por Gauss a los 19 años.

Ley de Reciprocidad Cuadrática (Gauss, 1796). Sean $p$ y $q$ primos impares distintos. Entonces:

En palabras: el producto $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = 1$ si al menos uno de $p, q$ es $\equiv 1 \pmod{4}$, y $= -1$ si ambos son $\equiv 3 \pmod{4}$. Esto permite "invertir" el símbolo: para calcular $\left(\frac{p}{q}\right)$ se puede calcular $\left(\frac{q}{p}\right)$ (que suele ser más sencillo) y usar la ley.

Demostración por conteo de puntos (argumento de Eisenstein)

La demostración más elegante usa un argumento de conteo de puntos reticulares en un rectángulo. Presentamos la idea principal.

Consideramos el rectángulo con vértices $(0,0)$, $(q/2, 0)$, $(q/2, p/2)$, $(0, p/2)$ en el plano. Los puntos con coordenadas enteras estrictamente interiores son los $(i, j)$ con $1 \le i \le \frac{q-1}{2}$ y $1 \le j \le \frac{p-1}{2}$, en total $\frac{p-1}{2} \cdot \frac{q-1}{2}$ puntos.

Dividimos estos puntos según si están por encima o por debajo de la diagonal $y = \frac{p}{q} x$. Ningún punto está exactamente sobre la diagonal (pues $p, q$ son primos distintos y $p \nmid qi$ para $i$ en el rango). Resulta que la cantidad de puntos por debajo de la diagonal es $\sum_{i=1}^{(q-1)/2} \lfloor \frac{pi}{q} \rfloor$, y la de puntos por encima es $\sum_{j=1}^{(p-1)/2} \lfloor \frac{qj}{p} \rfloor$.

Usando el Lema de Gauss en una versión equivalente (que identifica $\nu_p = \sum_{i=1}^{(q-1)/2} \lfloor \frac{pi}{q} \rfloor \bmod 2$), la suma total módulo 2 es $\nu_p + \nu_q \equiv \frac{p-1}{2} \cdot \frac{q-1}{2} \pmod{2}$. Esto da $(-1)^{\nu_p + \nu_q} = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$, que es exactamente la ley de reciprocidad.

Algoritmo de cálculo: uso sistemático de la reciprocidad

Con la ley de reciprocidad y las fórmulas para $\left(\frac{-1}{p}\right)$ y $\left(\frac{2}{p}\right)$, podemos calcular cualquier símbolo de Legendre mediante un proceso análogo al algoritmo de Euclides.

Ejemplo. Calcular $\left(\frac{105}{113}\right)$. Como $113$ es primo: $\left(\frac{105}{113}\right) = \left(\frac{3}{113}\right)\left(\frac{5}{113}\right)\left(\frac{7}{113}\right)$.

Para $\left(\frac{3}{113}\right)$: $113 \equiv 1 \pmod{4}$, así por reciprocidad $\left(\frac{3}{113}\right) = \left(\frac{113}{3}\right) = \left(\frac{2}{3}\right) = -1$ (pues $3 \equiv 3 \pmod{8}$). Para $\left(\frac{5}{113}\right)$: $113 \equiv 1 \pmod 4$, así $\left(\frac{5}{113}\right) = \left(\frac{113}{5}\right) = \left(\frac{3}{5}\right)$. Ahora $5 \equiv 1 \pmod 4$, así $\left(\frac{3}{5}\right) = \left(\frac{5}{3}\right) = \left(\frac{2}{3}\right) = -1$. Para $\left(\frac{7}{113}\right)$: $113 \equiv 1 \pmod 4$, así $\left(\frac{7}{113}\right) = \left(\frac{113}{7}\right) = \left(\frac{1}{7}\right) = 1$. En total: $\left(\frac{105}{113}\right) = (-1)(-1)(1) = 1$.

La estrategia es siempre: factorizar, aplicar reciprocidad para bajar el numerador, reducir módulo el denominador, y repetir.

Consecuencias para primos en progresiones aritméticas

Una aplicación clásica de la reciprocidad es determinar para cuáles primos $p$ un número fijo $a$ es residuo cuadrático.

Proposición. Sea $a$ un entero sin factores cuadrados. La condición $\left(\frac{a}{p}\right) = 1$ depende solo de la clase de $p$ módulo $4|a|$. En otras palabras, los primos para los cuales $a$ es RC forman una unión de clases de residuos módulo $4|a|$.

Ejemplo: $a = 5$. La reciprocidad da $\left(\frac{5}{p}\right) = \left(\frac{p}{5}\right)$ cuando $p \equiv 1 \pmod{4}$, y $\left(\frac{5}{p}\right) = -\left(\frac{p}{5}\right)$ cuando $p \equiv 3 \pmod{4}$. Resulta que $5$ es RC módulo $p$ si y solo si $p \equiv \pm 1 \pmod{5}$ y $p \equiv 1 \pmod 4$, o bien $p \equiv \pm 2 \pmod{5}$ y $p \equiv 3 \pmod 4$. Esto equivale a $p \equiv \pm 1 \pmod{5}$ (módulo 20, las clases $1, 9, 11, 19$). La verificación directa: $p = 11$, $4^2 = 16 \equiv 5 \pmod{11}$. Correcto.