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.

Page

Toolbox

Search

Quadratic residues

Legendre Symbol

Quadratic Reciprocity

Jacobi Symbol