Legendre Symbol is Multiplicative
Jump to navigation
Jump to search
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$