Legendre Symbol of Congruent Integers

Theorem

Let $p$ be a odd prime.

Let $a, b \in \Z$ be such that $a \equiv b \pmod p$.

Then:

$\paren {\dfrac a p} = \paren {\dfrac b p}$

where $\paren {\dfrac a p}$ is the Legendre symbol.

Proof

\(\ds \paren {\frac a p}\)

\(=\)

\(\ds a^{\frac {p - 1} 2} \bmod p\)

Definition 2 of Legendre Symbol

\(\ds \)

\(=\)

\(\ds b^{\frac {p - 1} 2} \bmod p\)

Congruence of Powers

\(\ds \)

\(=\)

\(\ds \paren {\frac b p}\)

Definition 2 of Legendre Symbol

$\blacksquare$