En teoría de números , un entero q se llama residuo cuadrático módulo n si es congruente con un cuadrado perfecto módulo n ; es decir, si existe un número entero x tal que:
Originalmente un concepto matemático abstracto de la rama de la teoría de números conocida como aritmética modular , los residuos cuadráticos ahora se utilizan en aplicaciones que van desde la ingeniería acústica hasta la criptografía y la factorización de grandes números .
Fermat , Euler , Lagrange , Legendre y otros teóricos de los números de los siglos XVII y XVIII establecieron teoremas [1] y formaron conjeturas [2] sobre residuos cuadráticos, pero el primer tratamiento sistemático es el § IV de las Disquisitiones Arithmeticae de Gauss (1801) . El artículo 95 introduce la terminología "residuo cuadrático" y "no residuo cuadrático", y establece que si el contexto lo aclara, se puede eliminar el adjetivo "cuadrático".
Para un n dado, se puede obtener una lista de los residuos cuadráticos módulo n simplemente elevando al cuadrado los números 0, 1, ..., n - 1 . Debido a que a 2 ≡ ( n - a ) 2 (mod n ), la lista de cuadrados módulo n es simétrica alrededor de n / 2, y la lista solo necesita llegar tan alto. Esto se puede ver en la siguiente tabla .
Por lo tanto, el número de residuos cuadráticos módulo n no puede exceder n / 2 + 1 ( n par) o ( n + 1) / 2 ( n impar). [3]
Módulo un número primo impar p hay ( p + 1) / 2 residuos (incluido 0) y ( p - 1) / 2 no residuos, según el criterio de Euler . En este caso, se acostumbra considerar 0 como un caso especial y trabajar dentro del grupo multiplicativo de elementos distintos de cero del campo Z / p Z. (En otras palabras, cada clase de congruencia excepto cero módulo p tiene un inverso multiplicativo. Esto no es cierto para módulos compuestos). [4]