Residuo cuadrático

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En Matemáticas, dentro de la Teoría de Números se denomina residuo cuadrático módulo p (donde p es un número primo) a cualquier entero r que no es múltiplo de p para el que tenga solución la congruencia:

x^2 \equiv r \pmod p,

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

En ocasiones se admite la definición de residuos cuadráticos módulo enteros no primos. Sin embargo, es conveniente limitarse al caso en el que el módulo es un primo p, ya que entonces tenemos un comportamiento mucho más sencillo. 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.

Ejemplo[editar]

Si tomamos el primo p=13, se tiene que 12 = 122 = 1 (mod 13), 22 = 112 = 4 (mod 13), 32 = 102 = 9 (mod 13), 42 = 92 = 3 (mod 13), 52 = 82 = 12 (mod 13), 62 = 72 = 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.

Notación[editar]

Suele utilizarse el símbolo de Legendre para marcar si un entero a es un residuo cuadrático módulo p. Dado un número a y un primo p, se define el mismo como:

\left ( \frac{a}{p} \right ) = 
\begin{cases}
\ \ 0 & \mbox{si } p \mbox{ divide a }a \\
\ \ 1 & \mbox{si } a\mbox{ es residuo cuadrático módulo } p \\
-1 & \mbox{si } a\mbox{ no es residuo cuadrático módulo } p \\

\end{cases}

Propiedades básicas[1] [editar]

  • El producto de dos residuos o de dos no-residuos es un residuo y el producto de un residuo y de un no-residuo es un no-residuo.
  • Si p es primo, la mitad de las p-1 clases residuales módulo p son residuos y la otra mitad no-residuos.
  • El criterio de Euler afirma que \left ( \frac{a}{p} \right ) = a^{\frac{p-1}2}\  (mod \ p). Esto significa que a es un residuo cuadrático módulo p si y solo si a^{\frac{p-1}2} = 1\ (mod \ p) .
  • -1 es un residuo de todos los primos de la sucesión 4k+1 y es un no-residuo de todos los primos de la sucesión 4k+3
  • 2 es un residuo de todos los primos de las sucesiones 8k+1 y 8k+7 y es un no-residuo de todos los demás primos impares.
  • Si p y q son primos impares, y ninguno de ellos pertenece a la sucesión 4k+1 entonces p es un residuo módulo q si y sólo si q es un no-residuo módulo p. Si por otro lado cualquiera de los dos, o ambos, pertenecen a la sucesión 4k+1 entonces p es un residuo módulo q si y sólo si q es un residuo módulo p.

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.

Algunas aplicaciones[editar]

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.[2]

Problemas abiertos y conjeturas[editar]

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 n(p). El mejor resultado conocido, debido a Burguess, asegura que la expresión

 \frac{n(p)}{p^{1/4\sqrt{e}}}

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

Extensiones[editar]

Al igual que de residuos cuadráticos, podemos hablar de residuos cúbicos, residuos bicuadráticos y en general de residuos potenciales.

Véase también[editar]

Referencias[editar]

  1. a b Miller, Steven; Takloo-Bighash, Ramin (2006). «Eisenstein's proof of quadratic reciprocity». An invitation to modern number theory (en inglés). Princeton, Nueva Jersey: Princeton University Press. pp. 22–23. ISBN 978-0-691-12060-7. 
  2. Koblitz, Neal (2006). «Pseudoprimes». A course in number theory and cryptography (en inglés) (segunda edición). Springer. p. 129. ISBN 0-387-94293-9. 

Enlaces externos[editar]