\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm,amsfonts,verbatim}
\usepackage{microtype}
\usepackage{enumerate}
\usepackage{url}

\addtolength{\evensidemargin}{-.6in}
\addtolength{\oddsidemargin}{-.6in}
\addtolength{\textwidth}{1.0in}
\addtolength{\textheight}{1.9in}
\addtolength{\topmargin}{-.7in}

\theoremstyle{plain}
\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{challenge}[theorem]{Challenge Problem}
\newtheorem*{theoremqr}{Theorem~\ref{thmqr}}

\title{\vspace{-50pt}Elementary Number Theory\\
\normalsize Math 175, Section 30, Autumn 2010\\
\large Shmuel Weinberger ({\tt shmuel@math.uchicago.edu})\\
Tom Church ({\tt tchurch@math.uchicago.edu})\\
\url{www.math.uchicago.edu/~tchurch/teaching/175/}}
\author{}
\date{}

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

% \DeclareMathOperator{\sin}{sin}   %% just an example (it's already defined)
\DeclareMathOperator{\norm}{norm}


\renewcommand{\baselinestretch}{1.2}
\begin{document}
\maketitle
\setcounter{section}{4}
\vspace{15pt}
\begin{center}
{\huge \bf Script 4: Quadratic Reciprocity}
\end{center}

\vspace{40pt}

\renewcommand{\baselinestretch}{1.2}

Fix a field $R$, and let $P(x)$ be a polynomial with coefficients in $R$; that is, \[P(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_2x^2+a_1x+a_0,\] with each $a_i\in R$. For any $r\in R$, we can evaluate the polynomial $P(x)$ at $r$ to give a value $P(r)\in R$, defined by
\[P(r)=a_nr^n+a_{n-1}r^{n-1}+\cdots+a_2r^2+a_1r+a_0\in R.\]
\begin{theorem}[Division algorithm for linear polynomials]
For any $u\in R$, we can write $P(x)=(x-u)\cdot Q(x)\ +\ P(u)$ for some polynomial $Q(x)$.
\end{theorem}


An element $r\in R$ is called a \emph{root} of the polynomial $P(x)$ if $P(r)=0$.
\begin{theorem}
If $r$ is a root of $P(x)$, then $P(x)=(x-r)\cdot Q(x)$ for some polynomial $Q(x)$.
\end{theorem}

\begin{exercise}
If $r_1,\ldots,r_k$ are distinct roots of $P(x)$, then \[P(x)=(x-r_1)(x-r_2)\cdots(x-r_k)\cdot Q(x)\] for some polynomial $Q(x)$.
\end{exercise}

\begin{theorem}
If $P(x)$ is a polynomial of degree $n$, then $P(x)$ has at most $n$ distinct roots.
\end{theorem}\vskip20pt
\pagebreak
\begin{definition}
Fix $m>1$ and suppose $(a,m)=1$.   If there exists $x\in\Z$ such that 
$x^2\equiv a\;\mbox{(mod $m$)}$, then $a$ is called a {\em quadratic residue (mod $m$)}.  
If there does not exist such an $x\in\Z$, then 
$a$ is called a {\em quadratic nonresidue (mod $m$)}.  
\end{definition}

\begin{definition}  
If $p$ is an odd prime and $(a,p)=1$, then the {\em Legendre symbol} $\displaystyle{\left(\frac{a}{p}\right)}$
is defined as follows:
$$
\left(\frac{a}{p}\right)=\left\{
\begin{array}{rl}
 +1, & \mbox{if $a$ is a quadratic residue (mod $p$)} \\
 -1, & \mbox{if $a$ is a quadratic nonresidue (mod $p$)}% \\
% 0, & \mbox{if $p|a$} \\
 \end{array}\right.
 $$
\end{definition}

\begin{theorem}
Let $p$ be an odd prime.  Then:
\begin{enumerate}[i.]
\item $\displaystyle{\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod{p}}$

\item
$\displaystyle{\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right)}$

\item
If $(a,p)=1$, then $\displaystyle{\left(\frac{a^2}{p}\right)=1}$
and $\displaystyle{\left(\frac{a^2b}{p}\right)=\left(\frac{b}{p}\right)}$.

\item
$\displaystyle{\left(\frac{1}{p}\right)=1}$ and 
$\displaystyle{\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}}$
\end{enumerate}
\end{theorem}\vskip25pt

\begin{definition}
Fix an odd integer $n>0$. We say that a subset $S\subset \{1,\ldots,n-1\}$ is a \emph{half-set} (modulo $n$) if \begin{enumerate}\item every element of $S$ is invertible modulo $n$, and \item for every $y$ which is invertible modulo $n$, either there exists $x\in S$ s.t. $y\equiv x\pmod{n}$ or there exists $x\in S$ s.t. $-y\equiv x\pmod{n}$, but not both.\end{enumerate} A half-set's purpose in life is to have all of its elements multiplied together: we write $\prod_S$ for the product $\prod_{s\in S}s$.
\end{definition}

\begin{theorem}
If $S$ and $T$ are both half-sets modulo $n$, then $\prod_S \equiv \pm\prod_T\pmod{n}$.
\end{theorem}\vskip25pt

\begin{lemma}
Let $p$ be an odd prime. Let $S$ be the half-set $S=\{1,\ldots,\frac{p-1}{2}\}$, and let $T=\{2,4,\ldots,p-1\}$. Then $T$ is a half-set modulo $p$ , and $\prod_T \equiv {\displaystyle \left(\frac{2}{p}\right)}\prod_S\pmod{p}$.\end{lemma}

\begin{theorem} Let $p$ be an odd prime. Then $\displaystyle{\left(\frac{2}{p}\right)}=1$ if $p\equiv 1$ or $p\equiv 7\pmod{8}$, while $\displaystyle{\left(\frac{2}{p}\right)}=-1$ if $p\equiv 3$ or $p\equiv 5\pmod{8}$. This can be summarized as
$\displaystyle{\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}}$.
\end{theorem}

\begin{lemma} Let $q$ be an odd prime. Then
$\left[\left(\frac{q-1}{2}\right)!\right]^2\equiv (-1)^{\frac{q-1}{2}}(-1)\pmod{q}$.
\end{lemma}
\pagebreak
In the remainder of this script, we prove Quadratic Reciprocity:
\begin{theorem}[Quadratic reciprocity] \label{thmqr} Let $p$ and $q$ be distinct odd primes. Then
\begin{itemize}
\item if $p\equiv 1\pmod{4}$ or $q\equiv 1\pmod{4}$,

$p$ is a quadratic residue$\pmod{q}$ if and only if $q$ is a quadratic residue$\pmod{p}$;
\item if $p\equiv 3\pmod{4}$ and $q\equiv 3\pmod{4}$,

 $p$ is a quadratic residue$\pmod{q}$ if and only if $q$ is \textbf{not} a quadratic residue$\pmod{p}$.
\end{itemize}
\end{theorem}

\begin{lemma}
This theorem can be summarized as: \[\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\]
\end{lemma}
\vskip25pt

For the rest of the sheet, fix odd primes $p$ and $q$.
Let \begin{align*}S&=\left\{\left.1\leq k\leq\frac{pq-1}{2}\right|(k,pq)=1\right\},\\A&=\left\{\left.1\leq k\leq\frac{pq-1}{2}\right|(k,p)=1\right\},\\\text{and }B&=\left\{\left.1\leq k\leq\frac{pq-1}{2}\right|q|k\right\}.\end{align*}

\begin{lemma} $S$ is a half-set modulo $pq$, the set $B$ is contained in the set $A$, and the set $S$ is the difference $A\setminus B$. Moreover we can write
\[A=\left\{a+px\left|1\leq a\leq p-1, 0\leq x<\frac{q-1}{2}\right.\right\}\cup\left\{a+px\left|1\leq a\leq \frac{p-1}{2}, x=\frac{q-1}{2}\right.\right\}\] and
\[B=\left\{qa\left|1\leq a\leq \frac{p-1}{2}\right.\right\}.\]
\end{lemma}

\begin{lemma} We have:\footnote{Both are mod $p$, this is not a typo.}
\begin{align*}{\textstyle\prod_A}&\equiv (p-1)!^{\frac{q-1}{2}}\left(\frac{p-1}{2}\right)!\quad\pmod{p}\\\text{and\quad}{\textstyle\prod_B}&\equiv q^{\frac{p-1}{2}}\left(\frac{p-1}{2}\right)!\quad\qquad\ \ \,\pmod{p}\end{align*}
\end{lemma}

\begin{lemma}
Show that \begin{align*}{\textstyle\prod_S}&\equiv (-1)^{\frac{q-1}{2}}\left(\frac{q}{p}\right)\quad\pmod{p}\\\text{and\quad}{\textstyle\prod_S}&\equiv (-1)^{\frac{p-1}{2}}\left(\frac{p}{q}\right)\quad\pmod{q}\end{align*}
\end{lemma}


\pagebreak Let \[T=\left\{k\in \Z\left\vert\begin{array}{l}1\leq k<pq\\k\equiv a \pmod{p}\text{ for }1\leq a\leq p-1\\k\equiv b \pmod{q}\text{ for }1\leq b\leq \frac{q-1}{2}\end{array}\right.\right\}\]

\begin{lemma} $T$ is a half-set modulo $pq$, with  \begin{align*}{\textstyle \prod_T}&\equiv \big[(p-1)!\big]^{\frac{q-1}{2}}\qquad\,\pmod{p}\\\text{and\quad}{\textstyle \prod_T}&\equiv \left[\left(\frac{q-1}{2}\right)!\right]^{p-1}\quad\pmod{q}.\end{align*} Conclude that \begin{align*}{\textstyle \prod_T}&\equiv (-1)^{\frac{q-1}{2}}\qquad\qquad\qquad\pmod{p}\\\text{and\quad}{\textstyle \prod_T}&\equiv (-1)^{\frac{q-1}{2}\frac{p-1}{2}}(-1)^{\frac{p-1}{2}}\quad\pmod{q}.\end{align*}
\end{lemma}

\begin{theorem}\begin{align*}\text{If }\left(\frac{q}{p}\right)\equiv\ \ 1\pmod{p},&\text{\quad then\quad\,\ }\left(\frac{p}{q}\right)\equiv (-1)^{\frac{p-1}{2}\frac{q-1}{2}}\pmod{q},\\\text{while if }\left(\frac{q}{p}\right)\equiv -1\pmod{p},&\text{\quad then }\,-\left(\frac{p}{q}\right)\equiv (-1)^{\frac{p-1}{2}\frac{q-1}{2}}\pmod{q}.\end{align*}
\end{theorem}\vskip30pt

\begin{theoremqr}[Quadratic reciprocity] Let $p$ and $q$ be distinct odd primes. Then
\begin{itemize}
\item if $p\equiv 1\pmod{4}$ or $q\equiv 1\pmod{4}$,

$p$ is a quadratic residue$\pmod{q}$ if and only if $q$ is a quadratic residue$\pmod{p}$;
\item if $p\equiv 3\pmod{4}$ and $q\equiv 3\pmod{4}$,

 $p$ is a quadratic residue$\pmod{q}$ if and only if $q$ is \textbf{not} a quadratic residue$\pmod{p}$.
\end{itemize}
\end{theoremqr}

%\begin{theorem}
%(The Chinese Remainder Theorem)
%
%Let $m_1, \ldots, m_r$ denote $r$ integers that are pairwise relatively prime, and let
%$a_1, \ldots, a_r$ be any integers.  Then the set of $r$ simultaneous congruences:
%\begin{center}
%$
%\begin{array}{ccl}
%x & \equiv & a_1\; \mbox{(mod $m_1$)} \\
%& \vdots & \\
%x & \equiv & a_r\; \mbox{(mod $m_r$)} \\
%\end{array}
%$
%\end{center}
%has a solution for $x$ in the integers.  Moreover, if $x_0$ is one solution, then every solution
%is of the form $x=x_0+k(m_1\cdots m_r)$ for some integer $k$.
%\end{theorem}

%2ZF7CLARG01FPF5

\end{document}