Equivalence of Definitions of Legendre Symbol

Theorem

Let $p$ be an odd prime.

Let $a \in \Z$.

The following definitions of the concept of Legendre Symbol are equivalent:

Definition 1

The Legendre symbol $\paren {\dfrac a p}$ is defined as:

$\paren {\dfrac a p} := \begin{cases} +1 & : a^{\frac {\paren {p - 1} } 2} \bmod p = 1 \\

0 & : a^{\frac {\paren {p - 1} } 2} \bmod p = 0 \\ -1 & : a^{\frac {\paren {p - 1} } 2} \bmod p = p - 1 \end{cases}$

Definition 2

The Legendre symbol $\paren {\dfrac a p}$ is defined as:

						\(\ds 0 \)		if $a \equiv 0 \pmod p$
						\(\ds +1 \)		if $a$ is a quadratic residue of $p$
						\(\ds -1 \)		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.