Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Quadratic residues"

 
m
Line 1: Line 1:
−
Let <math>a<math> and <math>m</math> be [[integer]]s, with <math>m\neq 0</math>. We say that <math>a</math> is a '''quadratic residue''' [[modulo]] <math>m</math> if there is some number <math>n</math> so that <math>n^2-a</math> is [[divisible]] by <math>m</math>.
+
Let <math>a</math> and <math>m</math> be [[integer]]s, with <math>m\neq 0</math>. We say that <math>a</math> is a '''quadratic residue''' [[modulo]] <math>m</math> if there is some number <math>n</math> so that <math>n^2-a</math> is [[divisible]] by <math>m</math>.
  
 
== Legendre Symbol ==
 
== Legendre Symbol ==

Revision as of 11:21, 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}$ (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.)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Quadratic_residues&oldid=4497"