Quadratic residues

Revision as of 11:21, 24 June 2006 by ComplexZeta (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Let $a<math> and <math>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}$ (Please fix this. It's too much like hard work for me right now.) 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.)