\documentclass[12pt]{amsart}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[all]{xy}
\usepackage{graphicx}
\usepackage[left = 1 in,top = 1 in, bottom=1in,right=1in]{geometry}
\begin{document}

\newcommand{\Q}{{\mathbb Q}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\F}{{\mathbb F}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\R}{{\mathbb R}}

\newtheorem{theorem}{Theorem} % (If you want theorem
\newtheorem{lemma}[theorem]{Lemma} % with section
\newtheorem{cor}[theorem]{Corollary} % goes for lemmas,
\newtheorem{prop}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{exam}[theorem]{Example}
\newtheorem{exer}[theorem]{Exercise}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{defn}{Definition}[theorem]

\numberwithin{equation}{section}


\title{Quadratic Reciprocity}

\author{ Jordan SCHETTLER}

\maketitle
\noindent {\bf Abstract.} \textit{The goals of this project are to have the reader(s) gain an appreciation for the usefulness of Legendre symbols and ultimately recreate Eisenstein's slick proof of Gauss's \textit{Theorema Aureum} of quadratic reciprocity.}


\section{Quadratic Residues and Legendre Symbols}

\begin{defn}
Let $m,n \in \Z$ with $(m,n)=1$ (recall:  the gcd $(m,n)$ is the nonnegative generator of the ideal $m\Z + n\Z$).  Then $m$ is called a \textbf{quadratic residue mod $n$} if $m \equiv x^2 \pmod{n}$ for some $x \in \Z$, and $m$ is called a \textbf{quadratic nonresidue mod $n$} otherwise. 
\end{defn}

Prove the following remark by considering the kernel and image of the map $x \mapsto x^2$ on the group of units $(\Z/n\Z)^{\times} = \{m + n\Z : (m,n)=1\}$.

\begin{remark}\label{group}
For $2 < n \in \N$ the set $\{m + n\Z : m \mbox{ is a quadratic residue mod } n\}$ is a subgroup of the group of units of order $\leq \varphi(n)/2$ where $\varphi(n) = \#(\Z/n\Z)^{\times}$ is the Euler totient function. If $n = p$ is an odd prime, then the order of this group is equal to $\varphi(p)/2 = (p-1)/2$, so the equivalence classes of all quadratic nonresidues form a coset of this group.
\end{remark}

\begin{defn}
Let $p$ be an odd prime and let $n \in \Z$. The \textbf{Legendre symbol} $(n/p)$ is defined as
\[\left(\frac{n}{p}\right) = \left\{ \begin{array}{rl} 1 & \mbox{if } n \mbox{ is a quadratic residue mod } p\\
-1 & \mbox{if } n \mbox{ is a quadratic nonresidue mod } p \\
0 & \mbox{if } p|n.
  \end{array} \right.  \]
\end{defn}

The law of quadratic reciprocity (the main theorem in this project) gives a precise relation-
ship between the ``reciprocal'' Legendre symbols $(p/q)$ and $(q/p)$ where $p, q$ are distinct odd
primes. We'll prove quadratic reciprocity in section 2, and we'll see applications thereof to
Diophantine equations and computations of Legendre symbols in section 3. In the meantime,
use remark \ref{group} to establish the following proposition.

\begin{prop}\label{prop}
Let $p$ be an odd prime and let $m, n \in \Z$. Then
\begin{equation}
\left(\frac{mn}{p}\right) = \left(\frac{m}{p}\right)\left(\frac{n}{p}\right)
\end{equation}
and
\begin{equation}
m \equiv n \pmod{p} \Rightarrow  \left(\frac{m}{p} \right) = \left(\frac{n}{p}\right).
\end{equation}
\end{prop}

Show the following lemma by recalling that an element of a finite group has order dividing the size of the group.

\begin{lemma}[Fermat's Little Theorem]\label{flt}
Let $p$ be an odd prime and let $n \in \Z$ with $(n,p)=1$. Then
\begin{equation}
n^{p-1} \equiv 1 \pmod{p}.
\end{equation}
\end{lemma}

Now apply lemma \ref{flt} to get the proceeding fundamental result about Legendre symbols (Hint: factor $n^{p-1}-1 = (n^{(p-1)/2}-1)(n^{(p-1)/2}+1)$ and use the fact that the group of units of a finite field is cyclic).

\begin{theorem}[Euler's Criterion]\label{ec}
Let $p$ be an odd prime and let $n \in \Z$ with $(n,p)=1$. Then
\begin{equation}
\left(\frac{n}{p} \right) \equiv n^{(p-1)/2} \pmod{p}.
\end{equation}
\end{theorem}

Next, plug in $n=-1$ into theorem \ref{ec} to get the following immediate consequence.

\begin{cor}
Let $p$ be an odd prime. Then
\begin{equation}
\left( \frac{-1}{p} \right) = (-1)^{(p-1)/2}.
\end{equation}
\end{cor}

\section{Quadratic Reciprocity}

Flesh out the sketch of the proof for the crucial lemma which follows where for $x \in \R$ we take $\lfloor x \rfloor := \max\{n \in \Z : n \leq x\}$.

\begin{lemma}[Eisenstein]\label{eis}
Let $p$ be an odd prime and let $n \in \Z$ with $(n, p) = 1$. Then
\begin{equation}
\left( \frac{n}{p} \right) = (-1)^s
\end{equation}
where
\[s = \sum_{k=1}^{(p-1)/2} \left\lfloor \frac{2kn}{p} \right\rfloor . \]
\end{lemma}

\begin{proof}[Sketch]
For each $k \in \{1, \ldots, (p-1)/2\}$ define
\[r_k :=  2kn - p\left\lfloor \frac{2kn}{p} \right\rfloor \equiv \left\lfloor \frac{2kn}{p} \right\rfloor \pmod{2}. \]
Then
\begin{eqnarray*}
n^{(p-1)/2} \prod_{k=1}^{(p-1)/2} (2k) & \equiv & \prod_{k=1}^{(p-1)/2} r_k = (-1)^{\sum_k r_k }   \prod_{k=1}^{(p-1)/2} [(-1)^{r_k} r_k] \\
& \equiv & (-1)^{\sum_k r_k } \prod_{k=1}^{(p-1)/2} (2k) \pmod{p},
\end{eqnarray*}
so by theorem \ref{ec} we get
\[\left( \frac{n}{p} \right) \equiv n^{(p-1)/2} \equiv (-1)^{\sum_k r_k} = (-1)^s \pmod{p}.   \]
\end{proof}

Deduce the following corollary which is traditionally established with a result called Gauss's lemma.

\begin{cor}
Let $p$ be an odd prime. Then
\begin{equation}
\left( \frac{2}{p} \right) = (-1)^{(p^2-1)/8}.
\end{equation}
\end{cor}

\begin{proof}
Note that
\[\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{4k}{p} \right\rfloor = \# \{k \in \N : p/4 < k \leq p/2  \} = \left\lfloor \frac{p}{2} \right\rfloor - \left\lfloor \frac{p}{4} \right\rfloor, \]
so if $p=8m \pm 1$, then
\[\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{4k}{p} \right\rfloor =  \left\lfloor 4m\pm 1/2 \right\rfloor - \left\lfloor 2m \pm 1/4 \right\rfloor = 2m \equiv 0 \equiv \frac{p^2-1}{8} \pmod{2} , \]
and if $p = 8m \pm 3$, then
\[\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{4k}{p} \right\rfloor =  \left\lfloor 4m\pm 3/2 \right\rfloor - \left\lfloor 2m \pm 3/4 \right\rfloor = 2m \pm 1 \equiv 1 \equiv \frac{p^2-1}{8} \pmod{2} . \]
\end{proof}

Finally, fill in the details of the following proof (originally suggested by Eisenstein) of the quadratic reciprocity theorem (originally proved by Gauss).

\begin{theorem}[Quadratic Reciprocity]\label{qr}
Let $p,q$ be distinct odd primes. Then
\begin{equation}
\left(\frac{p}{q}\right) \left(\frac{q}{p} \right) = (-1)^{[(p-1)/2][(q-1)/2]}.
\end{equation}
\end{theorem}

\begin{proof}[Sketch]

Consider the following diagram in the $(x, y)$-plane.

\begin{center}
\includegraphics[scale=0.7]{g39.jpg}
\end{center}

Let $\mu$ be the number of lattice points (i.e., points in the plane with integer coefficients) in the interior of the triangle $EFG$. Note that number of lattice points with odd $x$-coordinates in $EFG$ is equal to the number of lattice points with even $x$-coordinates in $BCE$, which has the same parity as the number of lattice points with even $x$-coordinates in $CEGH$. Hence
\[\mu \equiv \#\{P : P \mbox{ is a lattice point in } CFH \mbox{ and has even } x \mbox{-coordinate}\} \pmod{2},\]
but for each positive integer $m < p$, the number of lattice points in $CFH$ with $x$-coordinate $m$ is $\lfloor mq/p \rfloor$, so
\[\mu \equiv \sum_{k=1}^{(p-1)/2} \left\lfloor \frac{2kq}{p} \right\rfloor \pmod{2}.\]
Therefore lemma \ref{eis} now implies
\[\left( \frac{q}{p} \right) = (-1)^{\mu}. \]
A symmetric argument shows that
\[\left( \frac{p}{q} \right) = (-1)^{\nu}\]
where $\nu$ is the number of lattice points in $DEF$. Thus the statement follows from the observation
\[\mu + \nu = \#\{P : P \mbox{ is a lattice point in } DEGF\} = \frac{p-1}{2} \cdot \frac{q-1}{2}. \]

\end{proof}

\section{Examples and Applications}

\begin{remark}
For a fixed odd prime $p$, we can reasonably obtain the quadratic residues mod $p$ by simply squaring the integers $1, \ldots, (p-1)/2$ and reducing modulo $p$. On the other hand, the inverse problem of determining those primes $p$ for which a fixed integer $n$ is a quadratic residue mod $p$ requires reciprocity as the next example illustrates.
\end{remark}

\begin{exam}
To determine all odd primes $p$ for which $5$ is a quadratic residue mod $p$ we note that
\[ \left( \! \begin{array}{c} p \\ \hline 5 \end{array} \! \right) \left( \! \begin{array}{c} 5 \\ \hline  p \end{array} \! \right) = (-1)^{[(p-1)/2][(5-1)/2]} = 1, \]
so $(5/p)=1 \Leftrightarrow (p/5)=1 \Leftrightarrow p \equiv \pm 1 \pmod{5}$.
\end{exam}

\begin{exer}\label{cise}
Determine all odd primes $p$ for which $n=3$ is a quadratic residue mod $p$. Do the same for $n=7$ and $n=6$.
\end{exer}

The reciprocity law can also be utilized to compute Legendre symbols with ``large'' arguments as seen in the following example.

\begin{exam}
Suppose we wanted to compute $(21/53)$. We could start squaring the integers $1, \ldots, 26$ and reducing modulo $53$, but this would be laborious. It's easier to accomplish this by repeated applications of theorem \ref{qr} and proposition \ref{prop}; e.g.,
\begin{eqnarray*}
\left( \frac{21}{53} \right) &=& \left( \frac{3}{53} \right)\left( \frac{7}{53} \right) = \left( \frac{53}{3} \right) (-1)^{1 \cdot 26} \left( \frac{53}{7} \right) (-1)^{3 \cdot 26} = \left( \frac{2}{3} \right)\left( \frac{4}{7} \right) \\
&=& (-1)\left( \frac{2}{7}\right)^2 = (-1)(-1)^{(7^2-1)/4} = (-1)(-1)^{12} = -1.
 \end{eqnarray*}
\end{exam}

\begin{exer}
Use the techniques of the above example to compute $(143/409)$.
\end{exer}

Another use of quadratic reciprocity includes (as one would expect) finding integer solutions to degree two polynomial equations. Prove the following theorem by filling the details of the outline.

\begin{theorem}
Let $p$ be a prime. Then the equation $x^2 - 3y^2 = p$ has a solution in integers $x,y$  if and only if $p \equiv 1 \pmod{12}$.

\bigskip

\noindent Furthermore, the equation $3y^2 -x^2 = p$ has a solution in integers $x,y$ if and only if either $p \equiv -1 \pmod{12} \mbox{ or } p\in\{2,3\}$.
\end{theorem}

\bigskip

\begin{proof}
First handle the cases $p=2$ and $p=3$ using reduction modulo $3$ and $4$, respectively. Now suppose $p > 3$. If $p$ is of the form $\pm (x^2-3y^2)$ for some integers $x,y$, then $y$ is nonzero modulo $p$, so $3$ is a square modulo $p$. Conversely, suppose $3$ is a square modulo $p$. Then there are integers $m, n$ such that

\bigskip

\[mp=n^2-3=(n-\sqrt{3})(n+\sqrt{3}).\]

\bigskip

\noindent Thus $p$ divides the product $(n - \sqrt{3})(n + \sqrt{3})$ in the ring $\Z[\sqrt{3}]$, but $p$ does not divide $n \pm \sqrt{3}$ in $\Z[ \sqrt{3}]$, so $p$ is not a prime element in $\Z[ \sqrt{3}]$. Hence $p$ is not an irreducible element in $\Z[\sqrt{3}]$ since $\Z[\sqrt{3}]$ is a UFD (justify this), so there are $x,y,s,t \in \Z$ such that neither $x+y\sqrt{3}$ nor $s+t\sqrt{3}$ is a unit in $\Z[\sqrt{3}]$ and

\bigskip

\[p=(x+y\sqrt{3})(s+t\sqrt{3}).\]


\bigskip

\noindent Moreover, the norm map $N : \Z[\sqrt{3}] \rightarrow \Z$ given by $a + b\sqrt{3} \mapsto a^2 - 3b^2$ is multiplicative, so $p^2 = N(p) = (x^2 - 3y^2)(s^2 - 3t^2)$, but this implies $x^2 - 3y^2 = \pm p$ since only units have norm $\pm 1$. Now by exercise \ref{cise} (which used quadratic reciprocity) we know that

\bigskip

\[\left(\frac{3}{p} \right) = 1 \hspace{0.1 in} \mbox{ if and only if } \hspace{0.1 in} p \equiv \pm 1 \pmod{12}. \]

\bigskip

\noindent Finally, distinguish cases by reducing the expression $p = \pm(x^2-3y^2)$ modulo 3.

\end{proof}

\bibliographystyle{plain}
\begin{thebibliography}{7}

\bibitem{1} Pete L. Clark, Instructor's Name. ``Quadratic Reciproctity I.'' Course notes. Math 4400/6400 -- Number Theory. Course home page. Department of Mathematics, University of Georgia. http://math.uga.edu/$\sim$pete/4400qrlaw.pdf.

\bibitem{2} Kenneth Ireland and Michael Rosen, \textit{A Classical Introduction to Modern Number Theory}, 2th ed., Springer, 2000.

\bibitem{3} Reinhard C. Laubenbacher and David J. Pengelley, \textit{Eisenstein's Misunderstood Geometric Proof of the Quadratic Reciprocity Theorem}, The College Mathematics Journal, Vol. 25, No. 1, (Jan., 1994), pp. 29-34.

\end{thebibliography}

\end{document}