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 reciprocity"

m (Fixed denominators.)
(cleaned the LaTeX a bit; I'll add a proof later)
Line 1: Line 1:
−
Let <math>p</math> be a [[prime number|prime]], and let <math>a</math> be any integer not divisible by <math>p</math>. Then we can define the [[Legendre symbol]] <math>\left(\frac{a}{p}\right)=\begin{cases} 1 & a\mathrm{\ is\ a\ quadratic\ residue\ modulo\ } p, \\ -1 & \mathrm{otherwise}.\end{cases}</math>  
+
Let <math>p</math> be a [[prime number|prime]], and let <math>a</math> be any integer. Then we can define the [[Legendre symbol]]
 +
<cmath> \genfrac{(}{)}{}{}{a}{p} =\begin{cases} 1 & \text{if } a \text{ is a quadratic residue modulo } p, \\
 +
0 & \text{if } p \text{ divides } a, \\ -1 & \text{otherwise}.\end{cases} </cmath>
  
−
We say that <math>a</math> is a '''quadratic residue''' modulo <math>p</math> if there exists an integer <math>n</math> so that <math>n^2\equiv a\pmod p</math>. We can then define <math>\left(\frac{a}{p}\right)=0</math> if <math>a</math> is divisible by <math>p</math>.
+
We say that <math>a</math> is a '''quadratic residue''' modulo <math>p</math> if there exists an integer <math>n</math> so that <math>n^2\equiv a\pmod p</math>.
 +
 
 +
Equivalently, we can define the function <math>a \mapsto \genfrac{(}{)}{}{}{a}{p}</math> as the unique nonzero multiplicative [[homomorphism]] of <math>\mathbb{F}_p</math> into <math>\mathbb{R}</math>.
  
 
== Quadratic Reciprocity Theorem ==
 
== Quadratic Reciprocity Theorem ==
  
 
There are three parts. Let <math>p</math> and <math>q</math> be distinct [[odd integer | odd]] primes. Then the following hold:
 
There are three parts. Let <math>p</math> and <math>q</math> be distinct [[odd integer | odd]] primes. Then the following hold:
−
 
+
<cmath> \begin{align*}
−
* <math>\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}</math>.
+
\genfrac{(}{)}{}{}{-1}{p} &= (-1)^{(p-1)/2} , \\
−
* <math>\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}</math>.
+
\genfrac{(}{)}{}{}{2}{p} &= (-1)^{(p^2-1)/8} , \\
−
* <math>\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{(p-1)/2\ (q-1)/2}</math>.
+
\genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} &= (-1)^{(p-1)(q-1)/4} .
−
 
+
\end{align*} </cmath>
 
This theorem can help us evaluate Legendre symbols, since the following laws also apply:
 
This theorem can help us evaluate Legendre symbols, since the following laws also apply:
−
 
+
* If <math>a\equiv b\pmod{p}</math>, then <math>\genfrac{(}{)}{}{}{a}{p} = \genfrac{(}{)}{}{}{b}{p}</math>.
−
* If <math>a\equiv b\pmod{p}</math>, then <math>\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)</math>.
+
* <math>\genfrac{(}{)}{}{}{ab}{p}\right) = \genfrac{(}{)}{}{}{a}{p} \genfrac{(}{)}{}{}{b}{p}</math>.
−
* <math>\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)</math>.
 
  
 
There also exist quadratic reciprocity laws in other [[ring of integers|rings of integers]]. (I'll put that here later if I remember.)
 
There also exist quadratic reciprocity laws in other [[ring of integers|rings of integers]]. (I'll put that here later if I remember.)

Revision as of 21:09, 25 September 2008

Let $p$ be a prime, and let $a$ be any integer. Then we can define the Legendre symbol \[\genfrac{(}{)}{}{}{a}{p} =\begin{cases} 1 & \text{if } a \text{ is a quadratic residue modulo } p, \\ 0 & \text{if } p \text{ divides } a, \\ -1 & \text{otherwise}.\end{cases}\]

We say that $a$ is a quadratic residue modulo $p$ if there exists an integer $n$ so that $n^2\equiv a\pmod p$.

Equivalently, we can define the function $a \mapsto \genfrac{(}{)}{}{}{a}{p}$ as the unique nonzero multiplicative homomorphism of $\mathbb{F}_p$ into $\mathbb{R}$.

Quadratic Reciprocity Theorem

There are three parts. Let $p$ and $q$ be distinct odd primes. Then the following hold: \begin{align*} \genfrac{(}{)}{}{}{-1}{p} &= (-1)^{(p-1)/2} , \\ \genfrac{(}{)}{}{}{2}{p} &= (-1)^{(p^2-1)/8} , \\ \genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} &= (-1)^{(p-1)(q-1)/4} . \end{align*} This theorem can help us evaluate Legendre symbols, since the following laws also apply:

  • If $a\equiv b\pmod{p}$, then $\genfrac{(}{)}{}{}{a}{p} = \genfrac{(}{)}{}{}{b}{p}$.
  • $\genfrac{(}{)}{}{}{ab}{p}\right) = \genfrac{(}{)}{}{}{a}{p} \genfrac{(}{)}{}{}{b}{p}$ (Error compiling LaTeX. Unknown error_msg).

There also exist quadratic reciprocity laws in other rings of integers. (I'll put that here later if I remember.)

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