# Properties of Legendre Symbol

## Theorem

Let $p$ be an odd prime.

Let $a \in \Z$.

Let $\paren {\dfrac a p}$ be the Legendre symbol::

$\paren {\dfrac a p} := a^{\paren {\frac {p - 1} 2} } \pmod p$

$\paren {\dfrac a p} = 0$ if and only if $a \equiv 0 \pmod p$
$\paren {\dfrac a p} = 1$ if and only if $a$ is a quadratic residue mod $p$
$\paren {\dfrac a p} = -1$ if and only if $a$ is a quadratic non-residue mod $p$.

### Congruent Integers

If $a \equiv b \pmod p$, then:

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

### Multiplicative Nature

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

$\paren {\dfrac {a^2} p} = 1$

## Proofs

$\paren {\dfrac a p} = 0$ if and only if $a \equiv 0 \pmod p$:

Follows from Euler's Criterion.

$\paren {\dfrac a p} = 1$ if and only if $a$ is a quadratic residue mod $p$:

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

$\paren {\dfrac a p} = -1$ if and only if $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 $\paren {\dfrac a p} = \paren {\dfrac b p}$:

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

$\blacksquare$

### Proof of Multiplicative Nature

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

Follows directly from the identity:

$\paren {a b}^{\paren {\frac {p - 1} 2} } = a^{\paren {\frac {p - 1} 2} } b^{\paren {\frac {p - 1} 2} }$

$\blacksquare$

### Proof that Square is Quadratic Residue

$\paren {\dfrac {a^2} p} = 1$:

Follows directly from the definition.

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

$\blacksquare$