Órdenes y residuos cuadráticos · Definición

Criterio de Euler

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

Antes de empezar necesitas conocer

El criterio de Euler convierte la pregunta sobre residuos cuadráticos en un cálculo de potencia. Se apoya en el símbolo de Legendre y en el pequeño teorema de Fermat.

Definición

Criterio que permite decidir si un entero \(a\) es residuo cuadrático módulo un primo impar \(p\) mediante una potencia modular.

\[\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}\]

Para un primo impar \(p\) y un entero \(a\) con \(p\nmid a\), el símbolo de Legendre vale 1 o -1, y la potencia modular toma exactamente esos dos valores. Así se obtiene una prueba de residuo sin listar todos los cuadrados.

Tomemos \(p=7\) y \(a=3\). Como \(3^{3}=27\equiv -1\pmod 7\), el símbolo vale -1 y 3 no es residuo cuadrático módulo 7. En cambio, \(2^{3}\equiv 1\pmod 7\), luego 2 sí es residuo.

Un error frecuente es usar el exponente \(p-1\) en lugar de \((p-1)/2\), lo que siempre da 1 y no distingue residuos. Tampoco aplica el criterio cuando \(p\mid a\), caso en el que el símbolo vale 0.

Para pensar

¿Por qué el criterio usa \((p-1)/2\) y no \(p-1\)?

Porque \(a^{p-1}\equiv 1\pmod p\) por Fermat para todo \(a\) con \(p\nmid a\), y no distingue residuos.

Ejercicios 10

  1. Según el criterio de Euler, ¿a qué es congruente \(\left(\frac{a}{p}\right)\) módulo \(p\)?
  2. Para \(p=11\), ¿qué exponente \((p-1)/2\) usa el criterio?
  3. ¿Para qué primos \(p\) vale el criterio de Euler tal como se enuncia en esta ficha?
  4. Si \(a\) es residuo cuadrático módulo \(p\), ¿qué valor tiene \(a^{(p-1)/2}\bmod p\)?
  5. Si \(a^{(p-1)/2}\equiv -1\pmod p\), ¿qué puedes concluir sobre \(a\)?
  6. Usa el criterio para decidir si 3 es residuo cuadrático módulo 7. ¿Cuál es la conclusión correcta?
  7. Para \(p=13\) y \(a=5\), ¿cuál es el valor de \(5^{6}\bmod 13\) y qué significa?
  8. ¿Cuánto vale \(2^{(5-1)/2}\bmod 5\), y qué indica sobre \(2\)?
  9. Si \(a^{(p-1)/2}\equiv 1\pmod p\) y \(b^{(p-1)/2}\equiv 1\pmod p\), ¿a qué es congruente \((ab)^{(p-1)/2}\) módulo \(p\)?
  10. ¿Cuál de estas afirmaciones es falsa?

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