Difference between revisions of "Quadratic residues"

m
(Legendre Symbol: cleaned up the TeX a bit: \ is your friend)
Line 3: Line 3:
 
== Legendre Symbol ==
 
== Legendre Symbol ==
  
Determining whether <math>a</math> is a quadratic residue modulo <math>m</math> is easiest if <math>m=p</math> is a [[prime number|prime]]. In this case we write <math>\left(\frac{a}{p}\right)={0if pa,1if pa and a isaquadraticresiduemodulo p,1if pa and a isaquadraticnonresiduemodulo p.</math> (Please fix this. It's too much like hard work for me right now.) The symbol <math>\left(\frac{a}{p}\right)</math> is called the [[Legendre symbol]].
+
Determining whether <math>a</math> is a quadratic residue modulo <math>m</math> is easiest if <math>m=p</math> is a [[prime number|prime]]. In this case we write <math>\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}</math>  
 +
 
 +
The symbol <math>\left(\frac{a}{p}\right)</math> is called the [[Legendre symbol]].
  
 
== Quadratic Reciprocity ==
 
== Quadratic Reciprocity ==

Revision as of 12:30, 24 June 2006

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.)