Órdenes y residuos cuadráticos · Definición

Residuo cuadrático

teoría de números elementalórdenes y residuos cuadráticos

Antes de empezar necesitas conocer

Los residuos cuadráticos responden a una pregunta sencilla: qué números son cuadrados perfectos módulo n. Su estudio es la base de la reciprocidad cuadrática y de muchos algoritmos de primalidad.

Definición

Un residuo cuadrático módulo n es un entero a con mcd(a,n)=1 tal que la congruencia x² ≡ a (mod n) tiene solución. Si no tiene solución, a es un no residuo cuadrático.

\[x^2 \equiv a \pmod{p}\]

Si p es un primo impar, exactamente la mitad de las clases de restos no nulas módulo p son residuos cuadráticos, pues x² ≡ y² (mod p) equivale a y ≡ ±x (mod p). Por ello, los residuos forman un subconjunto de tamaño (p−1)/2 dentro de los restos no nulos.

Módulo 7, los cuadrados de 1, 2, 3 son 1, 4, 2. Así, los residuos cuadráticos no nulos son {1, 2, 4} y los no residuos son {3, 5, 6}, lo que se puede comprobar elevando cada resto a la potencia (7−1)/2 = 3 y comparando.

Un error típico es olvidar la condición mcd(a,n)=1: 0 o múltiplos de p cumplen x² ≡ a con solución, pero no se consideran residuos en el sentido estándar. Tampoco debe confundirse un residuo con la existencia de solución en módulos compuestos, donde el conteo cambia.

Para pensar

¿Para qué sirve el criterio de Euler \(a^{(p-1)/2}\) con \(p\) primo impar?

Decide si a es residuo sin listar cuadrados: es residuo si \(a^{(p-1)/2} \equiv 1 \pmod{p}\) y no residuo si \(a^{(p-1)/2} \equiv -1 \pmod{p}\).

Ejercicios 10

  1. ¿Cuál de estos enteros es un residuo cuadrático módulo 7?
  2. Enuncia la definición de residuo cuadrático módulo n para un entero a con mcd(a,n)=1.
  3. ¿Cuál es el conjunto de residuos cuadráticos no nulos módulo 5?
  4. Indica el número de residuos cuadráticos no nulos módulo un primo impar p.
  5. ¿Cuál de estos restos es un no residuo cuadrático módulo 11?
  6. Calcula los residuos cuadráticos no nulos módulo 9 y dime cuántos hay.
  7. Decide si 2 es residuo cuadrático módulo 17 calculando los cuadrados de los restos de 1 a 8.
  8. Resuelve x² ≡ 4 (mod 15) y cuenta cuántas soluciones módulo 15 hay.
  9. Determina si 3 es residuo cuadrático módulo 13 probando los cuadrados de 1 a 6.
  10. Sean \(p = 13\), \(a = 4\) y \(b = 9\), residuos cuadráticos módulo 13. Demuestra que \(ab\) también lo es y halla una raíz cuadrada de \(ab\) módulo 13.

Referencias

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 9
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 3