In number theory Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely, Let p be an odd prime and a an integer coprime to p. Then : a^{\tfrac{p-1}{2}} \equiv \begin{cases} \;\;\,1\pmod{p}& \text{ if there is an integer }x \text{ such that }a\equiv x^2 \pmod{p}\\ -1\pmod{p}& \text{ if there is no such integer.} \end{cases} Euler's criterion can be concisely reformulated using the Legendre symbol: : \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p. The criterion first appeared in a 1748 paper by Euler. Proof The pro...