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:

“Faith in reason as a prime motor is no longer the criterion of the sound mind, any more than faith in the Bible is the criterion of righteous intention.”
—George Bernard Shaw (1856–1950)