Residuos cuadráticos

En Matemáticas, dentro de la teoría de números se denomina residuo cuadrático módulo ${displaystyle m}$ a cualquier entero ${displaystyle r}$ coprimo con ${displaystyle m}$ para el que tenga solución la congruencia:

o lo que es lo mismo cuando ${displaystyle r}$ es un cuadrado no nulo módulo ${displaystyle m}$, y que por lo tanto tiene una raíz cuadrada en la aritmética de módulo ${displaystyle m}$.^[1]​^[2]​ A los enteros que no son congruentes con cuadrados perfectos módulo ${displaystyle m}$ se les denomina no-residuos cuadráticos. En adelante nos referimos a menudo a ellos como residuos y no-residuos.

En el estudio de los residuos cuadráticos es conveniente limitarse al caso en el que el módulo es un primo ${displaystyle p}$, ya que entonces tenemos un comportamiento mucho más sencillo, y muchas propiedades de los residuos para módulos generales pueden derivarse de este caso usando el teorema chino del resto, y otros resultados de la resolución de congruencias. Para estudiar este caso es muy conveniente el uso del símbolo de Legendre, y de su extensión el símbolo de Jacobi.

Si tomamos el primo p=13, se tiene que 1² = 12² ≡ 1 (mod 13), 2² = 11² ≡ 4 (mod 13), 3² = 10² ≡ 9 (mod 13), 4² = 9² ≡ 3 (mod 13), 5² = 8² ≡ 12 (mod 13), 6² = 7² ≡ 10 (mod 13).

Por lo tanto, los residuos cuadráticos módulo 13 son: 1, 3, 4, 9, 10 y 12; los no residuos: 2, 5, 6, 7, 8, y 11.

Gauss^[3]​ usó R y N para denotar residuos y no residuos, respectivamente;

A pesar de que esta notación es compacta y conveniente para algunos propósitos,^[4]​^[5]​ una mejor notación es el símbolo de Legendre, que también se conoce como carácter cuadrático, que se define para todos los números enteros a y números primos impares p como

Una ventaja de esta notación sobre la de Gauss es que el símbolo de Legendre es una función que puede usarse en fórmulas. Otra es que el símbolo se puede generalizar fácilmente a residuos cúbicos, residuos bicuadráticos y en general de residuos potenciales.^[6]​

A esta última propiedad se le conoce como la ley de reciprocidad cuadrática, y es uno de los teoremas más importantes de la teoría elemental de números.

Los residuos cuadráticos son útiles para varios test de primalidad, así como para algoritmos que permiten factorizar enteros. Se destaca entre ellos el test de primalidad de Solovay-Strassen, que utiliza el criterio de Euler junto a las propiedades del símbolo de Jacobi. Es un test probabilístico.^[7]​

Uno de los problemas abiertos más importantes sobre residuos cuadráticos es determinar el orden de magnitud del mínimo no-residuo cuadrático positivo ${displaystyle n(p)}$. El mejor resultado conocido, debido a Burguess, asegura que la expresión

está acotada para todos los primos, y se conjetura que el resultado podría seguir siendo cierto si sustituimos el denominador por ${displaystyle (log p)^{2}}$.