Quadratic residues

Let $a$ and $m$ be integers, with $m\neq 0$ . We say that $a$ is a quadratic residue modulo $m$ if there is some number $n$ so that $n^2-a$ is divisible by $m$ .

Legendre Symbol

Determining whether $a$ is a quadratic residue modulo $m$ is easiest if $m=p$ is a prime. In this case we write $\left(\frac{a}{p}\right)=\begin{cases} 0 & \mathrm{if }\ p\mid a, \\ 1 & \mathrm{if }\ p\nmid a\ \mathrm{ and }\ a\ \mathrm{\ is\ a\ quadratic\ residue\ modulo\ }\ p, \\ -1 & \mathrm{if }\ p\nmid a\ \mathrm{ and }\ a\ \mathrm{\ is\ a\ quadratic\ nonresidue\ modulo\ }\ p. \end{cases}$

The symbol $\left(\frac{a}{p}\right)$ is called the Legendre symbol.

Quadratic Reciprocity

Let $p$ and $q$ be distinct odd primes. Then $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$ . This is known as the Quadratic Reciprocity Theorem.

Jacobi Symbol

Now suppose that $m$ , as above, is not composite, and let $m=p_1^{e_1}\cdots p_n^{e_n}$ . Then we write $\left(\frac{a}{m}\right)=\left(\frac{a}{p_1}\right)^{e_1}\cdots\left(\frac{a}{p_n}\right)^{e_n}$ . This symbol is called the Jacobi symbol.

(I'm sure someone wants to write out all the fun properties of Legendre symbols. It just happens not to be me right now.)

Page

Toolbox

Search

Quadratic residues

Legendre Symbol

Quadratic Reciprocity

Jacobi Symbol