\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