Quadratic residues: Difference between revisions

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

@@ Line 3: / Line 3: @@
 == 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> (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 ==

Page

Toolbox

Search

Quadratic residues: Difference between revisions

Revision as of 12:30, 24 June 2006

Legendre Symbol

Quadratic Reciprocity

Jacobi Symbol