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:

“I divide all literary works into two categories: Those I like and those I don’t like. No other criterion exists for me.”
—Anton Pavlovich Chekhov (1860–1904)