Euler's Criterion | Euler 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 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.

Read more about Euler's Criterion: Proof, Examples

Famous quotes containing the word criterion:

“There is only one art, whose sole criterion is the power, the authenticity, the revelatory insight, the courage and suggestiveness with which it seeks its truth.... Thus, from the standpoint of the work and its worth it is irrelevant to which political ideas the artist as a citizen claims allegiance, which ideas he would like to serve with his work or whether he holds any such ideas at all.”
—Václav Havel (b. 1936)