Properties of Legendre Symbol

From ProofWiki
Jump to navigation Jump to search





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$


Quadratic Character

$\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}$


Square is Quadratic Residue

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


Proofs

Proof of Quadratic Character

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

Follows from Euler's Criterion for Quadratic Residue.


$\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 for Quadratic Residue.


$\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 for Quadratic Residue.

$\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$