Euler's Criterion
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
This theorem requires a proof. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code.If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page. |
Source of Name
This entry was named for Leonhard Paul Euler.
Sources
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Euler's criterion
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Euler's criterion