Legendre Symbol is Multiplicative

Theorem

Let $p$ be a odd prime.

Let $a, b \in \Z$.

Then:

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

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

Proof

We have:

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

\(=\)

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

Definition 2 of Legendre Symbol

\(\ds \)

\(=\)

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

Power of Product

\(\ds \)

\(=\)

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

Definition 2 of Legendre Symbol, Congruence of Product

$\blacksquare$