Euler's criterion

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 be an integer coprime to p. Then^[1][2][3]

${\displaystyle a^{\tfrac {p-1}{2}}\equiv {\begin{cases}\;\;\,1{\pmod {p}}&{\text{ if there is an integer }}x{\text{ such that }}x^{2}\equiv a{\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:^[4]

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

The criterion dates from a 1748 paper by Leonhard Euler.^[5][6]