Símbolo de Legendre y criterio de Euler

La pregunta que motiva el capítulo

Dado un primo $p$ y un entero $a$ con $p \nmid a$, ¿existe algún entero $x$ tal que $x^2 \equiv a \pmod{p}$? Parece una pregunta sencilla, pero su respuesta organiza toda la teoría de residuos cuadráticos y conduce a uno de los teoremas más profundos de la teoría de números elemental.

Este tipo de pregunta aparece naturalmente en olimpiadas cuando hay que decidir si una ecuación diofántica tiene solución módulo algún primo, o cuando se quiere construir un número que sea cuadrado perfecto módulo $p$ sin serlo en los enteros.

El instrumento que responde esta pregunta de manera compacta es el símbolo de Legendre, que codifica la respuesta en un solo número: $1$, $-1$ o $0$.

Residuos cuadráticos: definición y conteo

Sea $p$ un primo impar. Un entero $a$ con $p \nmid a$ es un **residuo cuadrático módulo $p$** si existe $x \in \mathbb{Z}$ con $x^2 \equiv a \pmod{p}$. En caso contrario, $a$ es un no-residuo cuadrático.

Los cuadrados no nulos módulo $p$ son $1^2, 2^2, \ldots, \left(\frac{p-1}{2}\right)^2$ módulo $p$. Nótese que $x^2 \equiv (p-x)^2 \pmod{p}$, así que cada residuo cuadrático tiene exactamente dos raíces cuadradas entre $1$ y $p-1$. En consecuencia, hay exactamente $\frac{p-1}{2}$ residuos cuadráticos y $\frac{p-1}{2}$ no-residuos cuadráticos entre $1$ y $p-1$.

Ejemplo con $p = 7$: los cuadrados son $1^2 = 1$, $2^2 = 4$, $3^2 = 2$ módulo 7. Los residuos cuadráticos son $\{1, 2, 4\}$ y los no-residuos son $\{3, 5, 6\}$. Efectivamente tres de cada tipo.

El símbolo de Legendre

El símbolo de Legendre de $a$ con respecto al primo $p$ se define como:

El valor $\left(\frac{a}{p}\right) = 1$ si $a$ es residuo cuadrático módulo $p$, $\left(\frac{a}{p}\right) = -1$ si $a$ es no-residuo cuadrático, y $\left(\frac{a}{p}\right) = 0$ si $p \mid a$.

El símbolo solo está definido cuando $p$ es primo impar. Para $p = 2$ la teoría es trivial: todo entero impar es cuadrado módulo 2.

El símbolo es completamente multiplicativo en $a$: $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$. Esta propiedad es fundamental y permite calcular el símbolo de productos sin factorizar completamente.

El criterio de Euler: cómo calcular el símbolo

El teorema central de esta lección da una fórmula explícita para el símbolo de Legendre sin necesidad de buscar raíces cuadradas.

Teorema (Criterio de Euler). Sea $p$ primo impar y $p \nmid a$. Entonces $\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}$.

Como $a^{(p-1)/2}$ es una raíz de $x^2 - 1 = (x-1)(x+1) \pmod{p}$ (por el Pequeño Teorema de Fermat, $a^{p-1} \equiv 1$), su valor módulo $p$ es $\pm 1$. El criterio afirma que este valor coincide con el símbolo.

Demostración. Si $a$ es residuo cuadrático, existe $x$ con $x^2 \equiv a$. Entonces $a^{(p-1)/2} \equiv x^{p-1} \equiv 1 \pmod{p}$ por Fermat. Si $a$ es no-residuo, hay que ver que $a^{(p-1)/2} \equiv -1$. Usamos raíces primitivas: sea $g$ una raíz primitiva módulo $p$ y $a = g^k$. Entonces $a$ es RC $\iff$ $k$ es par. Además $a^{(p-1)/2} = g^{k(p-1)/2} \equiv (-1)^k \pmod{p}$ (pues $g^{(p-1)/2} \equiv -1$ por ser el único elemento de orden 2). Por tanto el valor es $1$ si $k$ par (RC) y $-1$ si $k$ impar (NRC).

Propiedades del símbolo de Legendre

Del criterio de Euler se derivan varias propiedades inmediatas que usaremos constantemente:

Multiplicatividad: $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$. En particular $\left(\frac{a^2}{p}\right) = 1$ para todo $a$ con $p \nmid a$.

Periodicidad: Si $a \equiv b \pmod{p}$ entonces $\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$. El símbolo solo depende de la clase de $a$ módulo $p$.

**El caso $-1$:** $\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}$, es decir, $-1$ es residuo cuadrático módulo $p$ si y solo si $p \equiv 1 \pmod{4}$.

**El caso $2$:** $\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$, es decir, $2$ es residuo cuadrático módulo $p$ si y solo si $p \equiv \pm 1 \pmod{8}$. (Este resultado se demuestra en la Lección 5.2 usando el Lema de Gauss.)

Cálculo de $\left(\frac{-1}{p}\right)$: la demostración

El resultado sobre $-1$ merece una demostración detallada porque el argumento es un modelo para toda la teoría.

Por el criterio de Euler: $\left(\frac{-1}{p}\right) \equiv (-1)^{(p-1)/2} \pmod{p}$. Si $p \equiv 1 \pmod{4}$, entonces $(p-1)/2$ es par, así $(-1)^{(p-1)/2} = 1$. Si $p \equiv 3 \pmod{4}$, entonces $(p-1)/2$ es impar, así $(-1)^{(p-1)/2} = -1$.

Consecuencia olímpica. Todo primo $p \equiv 1 \pmod{4}$ puede escribirse como suma de dos cuadrados. Esta dirección del teorema de Fermat de dos cuadrados usa que $-1$ es RC módulo $p$: existe $x$ con $x^2 \equiv -1 \pmod{p}$, y el descenso sobre el retículo de Minkowski completa la demostración.

Ejemplo de aplicación. Para $p = 13 \equiv 1 \pmod{4}$: el criterio de Euler predice $\left(\frac{-1}{13}\right) = 1$. Verificamos: $5^2 = 25 \equiv 12 \equiv -1 \pmod{13}$. Efectivamente $-1$ es RC módulo 13.

Primer contacto con problemas olímpicos

Problema (IbAm, estilo). Demuestra que no existe ningún entero $x$ tal que $x^2 \equiv -3 \pmod{p}$ para primos $p \equiv 2 \pmod{3}$.

Solución. $\left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)$. Para primos $p \equiv 2 \pmod{3}$, usaremos en la próxima lección que $\left(\frac{3}{p}\right) = -\left(\frac{p}{3}\right)$ por reciprocidad. Como $p \equiv 2 \pmod{3}$, $\left(\frac{p}{3}\right) = \left(\frac{2}{3}\right) = -1$ (pues $2$ no es cuadrado módulo 3). Entonces $\left(\frac{3}{p}\right) = 1$. Por otro lado el valor de $\left(\frac{-1}{p}\right)$ depende de $p \bmod 4$. Para $p \equiv 2 \pmod{3}$ y $p \equiv 3 \pmod{4}$ (que es compatible), $\left(\frac{-1}{p}\right) = -1$, dando $\left(\frac{-3}{p}\right) = -1$. El problema completo requiere la reciprocidad cuadrática, que desarrollamos en la lección siguiente.

Lo importante ahora es el patrón: convertir la pregunta de existencia de raíz cuadrada en el cálculo del símbolo de Legendre, y luego factorizarlo usando multiplicatividad y el criterio de Euler.