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

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

${\displaystyle 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

${\displaystyle 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:

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

Demostración

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

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

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

${\displaystyle a^{(p-1)/2}}$	${\displaystyle \equiv (b^{i})^{(p-1)/2}{\pmod {p}}}$
	${\displaystyle \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 ${\displaystyle \pm b^{i/2}}$.