Residuos cuadráticos y reciprocidad

x²≡a módulo p pregunta si p divide x²−a. Solo importa la clase de x: cambiar x por x+kp no cambia su cuadrado módulo p. Para probar existencia basta recorrer los p restos posibles.

En esta lección p será primo impar, salvo los contraejemplos que indiquen otro módulo. Para a no divisible por p, llamamos residuo cuadrático a una clase con raíz y no residuo a una clase sin raíz. El resto cero se trata aparte: su única raíz módulo un primo es cero.

Supón r²≡a y a no nulo.

En un cuerpo un producto cero exige que uno de sus factores sea cero. Por tanto x≡r o x≡−r.

Las dos clases son distintas: r≡−r exigiría 2r≡0, imposible con p impar y r no nulo. Los p−1 restos no nulos se agrupan en parejas {r,−r}; por eso hay exactamente (p−1)/2 residuos cuadráticos no nulos. El argumento del producto exige primalidad.

Para p primo impar, el símbolo (a/p) vale cero si p divide a, uno si a es un residuo no nulo, y menos uno si no lo es. La barra de esta notación no es una división: el símbolo solo devuelve −1,0,1.

Podemos reducir a módulo p antes de empezar. Que el símbolo valga uno garantiza dos raíces, pero no nos dice cuáles. Encontrarlas es otro problema. El denominador del símbolo de Legendre debe ser primo impar; no se usa la definición como si valiera sin cambios para cualquier entero.

El criterio de Euler dice a^h≡(a/p) módulo p. Si a es cero módulo p, ambos lados son cero. Si es no nulo, Fermat da (a^h)²≡1, de modo que a^h solo puede ser uno o menos uno.

Ya tenemos h cuadrados distintos que son raíces del polinomio X^h−1. Un polinomio de grado h sobre un cuerpo tiene como máximo h raíces. Así no quedan otras clases con potencia uno; las clases restantes tienen potencia menos uno. Esta cuenta prueba el criterio completo.

El criterio de Euler aplicado a ab da (ab)^h≡a^h b^h. Si ningún factor es cero módulo p, los valores ±1 son distintos porque p es impar; por tanto (ab/p)=(a/p)(b/p). Si un factor es cero, los dos lados de esta identidad son cero y la regla también vale.

Un factor cuadrado no nulo aporta uno al símbolo. Podemos eliminarlo para simplificar la decisión, pero eliminarlo no conserva las raíces concretas. Dos no residuos multiplicados dan un residuo; el símbolo registra signos multiplicativos.

Su valor es uno para p≡1 módulo cuatro y menos uno para p≡3 módulo cuatro. Equivale a preguntar si el exponente es par o impar.

El exponente es entero para p impar. Su valor es uno si p≡1 o 7 módulo ocho, y menos uno si p≡3 o 5 módulo ocho. Lo justificaremos contando signos con Gauss; no hace falta memorizar una lista de primos.

Dicho como regla de cálculo: al intercambiar numerador y denominador, el signo cambia exactamente cuando ambos primos son tres módulo cuatro.

La utilidad es que, después de intercambiar, podemos reducir el nuevo numerador. Esa reducción suele hacer el problema menor. Primero sacamos los factores dos y menos uno, y comprobamos que los otros factores del numerador sean primos antes de intercambiarlos individualmente.

Multiplica 1,…,h por a y representa cada resto entre −h y h, excluyendo cero. Sea N el número de representantes negativos.

Sus valores absolutos son una permutación de 1,…,h. Si dos coincidieran, tendríamos aj≡±ak; al cancelar a, o bien j=k, o bien j+k=p.

Multiplicar los representantes da a^h h!≡(-1)^N h!. Cancelamos h!, que no contiene el primo p, y usamos Euler.

Son negativos al centrar exactamente cuando superan p/2: N=h−⌊p/4⌋.

Sus paridades prueban el suplemento de dos.

Ahora probamos la regla, sin pedir que aceptes un signo misterioso.

Definimos S como la suma de ⌊qi/p⌋ para i=1,…,h, y T como la suma de ⌊pj/q⌋ para j=1,…,k. Cada parte entera contará puntos de una columna o fila.

Como p y q son impares, la suma de los rᵢ tiene la misma paridad que la suma de i menos S. Al centrar, los valores absolutos son 1,…,h; cada representante negativo cambia su resto positivo de s a p−s, una diferencia impar. Por tanto esa misma suma tiene paridad igual a la suma de i más N.

No hay puntos en la recta pj=qi: con primos distintos eso exigiría p dividir i, que está entre uno y h. En cada columna, ⌊qi/p⌋ cuenta los puntos por debajo; qi/p<q/2 garantiza que todos están dentro del rectángulo. Por filas, ⌊pj/q⌋ cuenta los de encima.

Es justamente reciprocidad. El signo es negativo solo cuando h y k son impares, es decir, cuando ambos primos son tres módulo cuatro.

Un procedimiento seguro es reducir el numerador, separar el caso cero, extraer cuadrados no nulos, factorizar lo que quede y aplicar los suplementos o reciprocidad a primos impares distintos. Cuando el símbolo sea uno, todavía falta un método para hallar raíces si el ejercicio las pide.

Para un denominador impar compuesto se define el símbolo de Jacobi multiplicando los símbolos de Legendre de sus factores primos, con sus multiplicidades. Puede valer uno sin que exista raíz. Es una herramienta distinta; el certificado de existencia de Legendre depende de la primalidad del denominador.