Criterio de Euler
# 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}\equiv 1{\pmod {p}}.$

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

    $a^{(p-1)/2}\equiv -1{\pmod {p}}.$

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

    $a^{(p-1)/2}\equiv \left({\frac {a}{p}}\right){\pmod {p}}.$

## Demostración

Supóngase que $a\equiv x^{2}{\pmod {p}}$. 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 $a^{p-1}\equiv 1{\pmod {p}}$. Luego se tiene que

    $a^{(p-1)/2}$ $\equiv (x^{2})^{(p-1)/2}{\pmod {p}}$ $\equiv x^{p-1}{\pmod {p}}$ $\equiv 1{\pmod {p}}$

A la inversa, se supone que $a^{(p-1)/2}\equiv 1{\pmod {p}}$. Sea b un elemento primitivo módulo p. Entonces $a\equiv b^{i}{\pmod {p}}$ para algún i. Luego se tiene que

    $a^{(p-1)/2}$ $\equiv (b^{i})^{(p-1)/2}{\pmod {p}}$ $\equiv b^{i(p-1)/2}{\pmod {p}}$

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 $\pm b^{i/2}$.

