Euler's Criterion

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $a$ be a residue order $n$ of $m$, where $a$ and $m$ are coprime.

Then:

$a^{\map \phi m / d} \equiv 1 \pmod m$

where:

$\map \phi m$ denotes the Euler $\phi$ function of $m$
$d$ denotes the gretest common divisor of $\map \phi m$ and $n$
$\equiv$ denotes modulo congruence.


Euler's Criterion for Quadratic Residue

Let $p$ be an odd prime.

Let $a \not \equiv 0 \pmod p$.

Then:

\(\ds a^{\frac {p-1} 2}\) \(\equiv\) \(\ds 1\) \(\ds \pmod p\) if and only if $a$ is a quadratic residue of $p$
\(\ds a ^{\frac {p-1} 2}\) \(\equiv\) \(\ds -1\) \(\ds \pmod p\) if and only if $a$ is a quadratic non-residue of $p$.


Proof




Source of Name

This entry was named for Leonhard Paul Euler.


Sources