Criterio de Euler

En teoría de números, concretamente en aritmética modular, el criterio de Euler es utilizado para calcular si un número entero x es un residuo cuadrático módulo un número primo. Su nombre se debe al matemático suizo Leonhard Euler.

Enunciado

Sea p > 2 un número primo y a un número entero coprimo con p. Entonces a es un residuo cuadrático módulo p si y solo si

a(p−1)/2≡1(modp).

Como corolario de este teorema se obtiene que si a no es un residuo cuadrático módulo p entonces

a(p−1)/2≡−1(modp).

Así, el criterio de Euler puede ser reformulado de manera más compacta usando el símbolo de Legendre:

a(p−1)/2≡(ap)(modp).

Demostración

Supóngase que a≡x2(modp). Se sabe por el pequeño teorema de Fermat que si p es primo y es coprimo con a, es decir, p no divide al número a, entonces ap−1≡1(modp). Luego se tiene que

a(p−1)/2 ≡(x2)(p−1)/2(modp)
≡xp−1(modp)
≡1(modp)

A la inversa, se supone que a(p−1)/2≡1(modp). Sea b un elemento primitivo módulo p. Entonces a≡bi(modp) para algún i. Luego se tiene que

a(p−1)/2 ≡(bi)(p−1)/2(modp)
≡bi(p−1)/2(modp)

Como b es de orden p-1, debe darse el caso de que p-1 divide a i(p-1)/2. Por lo tanto, i es par, y las raíces cuadradas de a son ±bi/2.