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.
[1][2][3] 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 Como corolario de este teorema se obtiene que si a no es un residuo cuadrático módulo p entonces Así, el criterio de Euler puede ser reformulado de manera más compacta usando el símbolo de Legendre: Supóngase que
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
Luego se tiene que A la inversa, se supone que
Sea b un elemento primitivo módulo p. Entonces
para algún i.
Luego se tiene que 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