Criterio de Euler (para residuos cuadráticos)

La condición es necesaria: Supongamos que existe un entero $x$ que resuelve $x^2\equiv a\pmod p$. Por Fermat, sabemos que $a^{p-1}\equiv 1\pmod p$. Pero, por hipótesis, $a$ es equiresidual con $x^2$. Entonces, módulo $p$,

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

La condición es suficiente: Supongamos que $a^{(p-1)/2}\equiv 1\pmod{p}$, y tomemos una raíz primitiva $g$ de $p$. Entonces $a$ es equiresidual con alguna potencia de $g$ --digamos con $g^i$-- en la división entre $p$. Entonces, módulo $p$, $$1 \equiv x^{(p-1)/2} \equiv (g^i)^{(p-1)/2} \equiv g^{i(p-1)/2}$$ . Es decir,$1\equiv {g^{i(p-1)/2}}$. Ahora recordemos que, puesto que $p$ es primo, el orden de $g$ es $p-1$ --por definición de raíz primitiva. Así que, por teorema conocido, el exponente $i(p-1)/2$ es múltiplo de $p-1$. De aquí que $i$ sea par --digamos $i=2k$. Es decir, $g^i=g^{2k}=(g^k)^2$, y hemos encontrado un cuadrado perfecto que es equiresidual con $a$ en la división entre $p$. En otras palabras, $a$ es residuo cuadrático de $p$.