Properties of Legendre Symbol

Let $p$ be an odd prime.

Let $a \in \Z$.

Let $\displaystyle \left({\frac{a}{p}}\right)$ be the Legendre symbol: $\displaystyle \left({\frac{a}{p}}\right) \ \stackrel {\mathbf {def}} {=\!=} \ a^{\left({\frac {p-1}2}\right)} \pmod p$.

Theorems

Quadratic Character

• $\displaystyle \left({\frac{a}{p}}\right) = 0$ iff $a \equiv 0 \pmod p$;
• $\displaystyle \left({\frac{a}{p}}\right) = 1$ iff $a$ is a Quadratic Residue mod $p$;
• $\displaystyle \left({\frac{a}{p}}\right) = -1$ iff $a$ is a Quadratic Non-Residue mod $p$.

Congruent Integers

If $a \equiv b \pmod p$, then $\displaystyle \left({\frac{a}{p}}\right) = \left({\frac{b}{p}}\right)$.

Multiplicative Nature

• $\displaystyle \left({\frac{a b}{p}}\right) = \left({\frac{a}{p}}\right) \left({\frac{b}{p}}\right)$.

Square is Quadratic Residue

• $\displaystyle \left({\frac{a^2}{p}}\right) = 1$.

Proofs

Proof of Quadratic Character

• $\displaystyle \left({\frac{a}{p}}\right) = 0$ iff $a \equiv 0 \pmod p$;

Follows from Euler's Criterion.

• $\displaystyle \left({\frac{a}{p}}\right) = 1$ iff $a$ is a Quadratic Residue mod $p$:

This follows directly from the definition of quadratic residue and Euler's Criterion.

• $\displaystyle \left({\frac{a}{p}}\right) = -1$ iff $a$ is a Quadratic Non-Residue mod $p$:

This follows directly from the definition of Quadratic Non-Residue and Euler's Criterion.

$\blacksquare$

Proof of Congruent Integers

If $a \equiv b \pmod p$, then $\displaystyle \left({\frac{a}{p}}\right) = \left({\frac{b}{p}}\right)$:

This is just a statement of the quadratic character of congruent integers.

$\blacksquare$

Proof of Multiplicative Nature

$\displaystyle \left({\frac{a b}{p}}\right) = \left({\frac{a}{p}}\right) \left({\frac{b}{p}}\right)$:

Follows directly from the identity $\displaystyle \left({a b}\right)^{\left({\frac {p-1}2}\right)} = a^{\left({\frac {p-1}2}\right)} b^{\left({\frac {p-1}2}\right)}$.

$\blacksquare$

Proof that Square is Quadratic Residue

$\displaystyle \left({\frac{a^2}{p}}\right) = 1$:

Follows directly from the definition.

Alternatively, it also follows from the fact that the Legendre symbol is multiplicative.

$\blacksquare$