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

\addtolength{\evensidemargin}{-.6in}
\addtolength{\oddsidemargin}{-.6in}
\addtolength{\textwidth}{1.0in}
\addtolength{\textheight}{2.1in}
\addtolength{\topmargin}{-.8in}

\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*{theoremp}{Theorem~\ref{squaremodp}}

\title{\vspace{-20pt}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}{3}
\vspace{15pt}
\begin{center}
{\huge \bf Script 3: Congruence in the Integers}
\end{center}

\vspace{40pt}

\renewcommand{\baselinestretch}{1.5}
\begin{definition}
Fix $n\in\Z$ with $n>1$.  We say that two integers $a$ and $b$ are {\em congruent modulo $n$}
and write $a\equiv b\pmod{n}$ provided that $n\,|\,(b-a)$.
\end{definition}

\begin{theorem}
Fix $n>1$.  Then congruence modulo $n$ is an equivalence relation on $\Z$.  That is:
\begin{enumerate}
\item[(i)]  If $a\in \Z$, then $a\equiv a\pmod{n}$.

\item[(ii)]  If $a, b\in \Z$, then $a\equiv b\pmod{n}$ if and only if $b\equiv a\pmod{n}$.

\item[(iii)]  If $a, b, c\in \Z$ and $a\equiv b\pmod{n}$ and $b\equiv c\pmod{n}$, then 
$a\equiv c\pmod{n}$.
\end{enumerate}
\end{theorem}

\begin{theorem}
If $a\equiv b\pmod{n}$ and $c\equiv d\pmod{n}$, then
\begin{enumerate}
\item[(i)]
$a+c\equiv b+d\pmod{n}$

\item[(ii)]
$a\cdot c\equiv b\cdot d\pmod{n}$
\end{enumerate}
\end{theorem}

\begin{theorem}
If $a\equiv b\pmod{n}$, then $ac\equiv bc\pmod{nc}$ for any $c>0$.
\end{theorem}

\begin{theorem}
If $(a, n)=1$, then there exists $b\in\Z$ such that $a\cdot b \equiv 1\pmod{n}$.
\end{theorem}

\begin{theorem}
Given $c\in\Z$, if $(a, n)=1$, 
then the congruence $ax\equiv c\pmod{n}$ has a solution for $x$ in 
the integers.
\end{theorem}
\pagebreak
\begin{exercise}  Solve the following congruences for $x$:
\begin{enumerate}
\item[a)]  $3x\equiv 1\pmod{7}$

\item[b)]  $8x\equiv 11\pmod{23}$

\item[c)]  $25x+1\equiv 0\pmod{126}$

\item[d)]  $22x\equiv 2\pmod{178}$
\end{enumerate}
\end{exercise}

\begin{theorem}
If $a$ and $n$ are relatively prime, then \vskip-20pt
\[ax\equiv ay\pmod{n} \quad\text{if and only if}\quad
x\equiv y\pmod{n}.\]
\end{theorem}

\begin{theorem}
If $m=(a, n)$, then \vskip-20pt
\[ax\equiv ay\pmod{n} \quad\text{if and only if}\quad
x\equiv y\pmod{\frac{n}{m}}.\]
\end{theorem}\vskip20pt

\begin{definition}
A number system (a collection of elements equipped with an addition operation and a multiplication operation) is called a \emph{commutative ring with identity} (\mbox{sometimes} just called a \emph{ring} if the context is clear) if it satisfies Axioms A1--A5, M1--M4, and D.
\end{definition}

\begin{definition}
A number system is called a \emph{field} if it satisfies Axioms A1--A5, M1--M4, and D (i.e. it is a ring), and in addition satisfies Axiom M5, which states that every nonzero element has a multiplicative inverse:
\begin{enumerate}
{\bf \item[M5.]  (Multiplicative Inverses)}
For each nonzero element $a\neq 0$, there is a unique element $a^{-1}$ such that $a\cdot a^{-1}=1$ and $a^{-1}\cdot a=1$.
\end{enumerate}
\end{definition}
\vskip20pt

\begin{definition} Fix $n\in \Z$ with $n>1$. For an integer $a\in \Z$, the \emph{residue class  of $a$ modulo $n$}, or sometimes just the \emph{residue class of $a$}, is the set of all integers congruent to $a$ (mod $n$):
\[[a]=\big\{b\in \Z\ \big\vert\ a\equiv b\pmod{n}\big\}\]
\end{definition}

\begin{exercise} Given $a,b\in \Z$, we have
\[[a]=[b]\quad\text{if and only if}\quad a\equiv b\pmod{n}\]
\end{exercise}

\begin{theorem}
The number of distinct residue classes modulo $n$ is $n$.
\end{theorem}

\begin{theorem}
If $[a]=[b]$, then $(a,n)=(b,n)$.
\end{theorem}

\begin{definition}
Fix $n>1$.
We define the number system $\Z/n\Z$ to be the set of residue classes modulo $n$. We define
addition and multiplication in $\Z/n\Z$ as follows:
\begin{align*}
[a]+[b]&=[a+b]\qquad\qquad\text{ for $a,b\in \Z$}\\
[a]\cdot[b]\ \,&=[a\cdot b]\qquad\qquad\ \,\text{ for $a,b\in \Z$}
\end{align*}
\end{definition}

\begin{theorem}
Show that addition and multiplication are well-defined in 
$\Z/n\Z$.
\end{theorem}


\begin{exercise}
Check that $\Z/n\Z$ is a commutative ring with identity for any $n>1$.
\end{exercise}

\begin{theorem}
Show that $\Z/p\Z$ is a field if and only if $p$ is prime.
\end{theorem}\vskip20pt


\begin{theorem}
If $p$ is prime and $a,b\in \Z/p\Z$, then $a\neq 0$ and $b\neq 0$ implies $ab\neq 0$.
\end{theorem}

\begin{definition}If $R$ is a commutative ring with identity, then an element $x\in R$ is called a \emph{unit} if $x$ has a multiplicative inverse in $R$. We write $R^{\times}$ (pronounced ``R-cross'') for the set of invertible elements:
\[R^\times=\big\{x\in R\big|x\cdot y=1\text{ for some }y\in R\big\}\]
\end{definition}

\begin{theorem}
For any ring $R$, the set $R^\times$ is closed under multiplication.
\end{theorem}\vskip20pt

\begin{theorem}[Wilson's Theorem]
If $p$ is prime, then $(p-1)!\equiv -1\; \pmod{p}$.\newline
(It may be helpful to consider $p=2$ as a separate case.)
\end{theorem}

\begin{exercise}
If $p$ is prime and $a\in \Z/p\Z$ is nonzero, the sets\newline \phantom{x}\qquad\qquad\qquad$\big\{x\big|x\in \Z/p\Z, x\neq 0\big\}$\quad and\quad $\big\{ax\big|x\in \Z/p\Z, x\neq 0\}$\quad are equal.
\end{exercise}

\begin{theorem}
If $p$ is prime and $a\in\Z$ with $p\not| \,a$, then
$a^{p-1}\equiv 1\; \pmod{p}$.
\end{theorem}

\begin{theorem}[Fermat's Little Theorem]
If $p$ is prime and $a\in\Z$, then
$a^p\equiv a\; \pmod{p}$.
\end{theorem}\vskip20pt

\begin{theorem}
Let $p$ be prime.  Then 
$x^2\equiv 1\; \pmod{p}$ if and only if $x\equiv \pm 1\; \pmod{p}$.
\end{theorem}

\begin{theorem}
Let $p$ be an odd prime.  Then the congruence
$x^2\equiv -1\; \pmod{p}$ has solutions 
if and only if $p\equiv 1\pmod{4}$.
\end{theorem}

\begin{exercise}
If $q$ is prime and $q\equiv 3\pmod{4}$, and $d\in \Z/q\Z$, then $d$ and $-d$ cannot both be squares\footnote{As you would expect, an element of a ring is called a \emph{square} if it is equal to $y^2$ for some element $y$.}  in $\Z/q\Z$. 
\end{exercise} 

\begin{theorem}
\label{squaremodq}
Let $q$ be a prime factor of $a^2+b^2$. 
If $q\equiv 3\pmod{4}$, then $q|a$ and $q|b$.
\end{theorem} \pagebreak
We state the next theorem before giving a sequence of lemmas that leads to its proof.

\begin{theorem}
\label{squaremodp}
If $p$ is a prime such that $p\equiv 1\pmod{4}$, there exist
integers $a, b$ such that \[p=a^2+b^2.\]
\end{theorem}\vskip10pt

\noindent
For Lemmas~\ref{firstlemma} through \ref{lastlemma}, assume the following:

\begin{itemize}
\item[]
Let $p$ be prime such that $p\equiv 1\; \pmod{4}$.

\vspace{-10pt}
\item[]
Let $k$ be the greatest integer less than $\sqrt{p}$, and let $S=\{0, 1, \ldots, k\}$.

\vspace{-10pt}
\item[]
Let $x$ be an integer such that $x^2\equiv -1\; \pmod{p}$ (as per Thm.\ 30). 
\end{itemize}

\begin{lemma}\label{firstlemma}
$|S\times S|>p$.
\end{lemma}

\begin{lemma}
There exist two distinct pairs $(u_1, v_1), (u_2, v_2)\in S\times S$ such that
$$u_1+xv_1\equiv u_2+xv_2\; \pmod{p}.$$
\end{lemma}

With $u_1, u_2, v_1, v_2$ from the preceding lemma, let $a=u_1-u_2$ and $b=v_1-v_2$.

\begin{lemma}
$a^2+b^2\equiv 0\; \pmod{p}$ .
\end{lemma}

\begin{lemma}\label{lastlemma}
$0<a^2+b^2<2p$.
\end{lemma}

\begin{theoremp}
$p=a^2+b^2$.
\end{theoremp}\vskip10pt

\begin{exercise}
\label{foil}
For any integers (or real numbers, for that matter), 
$$(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2.$$
\end{exercise}\vskip20pt

\begin{theorem}
Let $n$ be an integer greater than 1.  Suppose 
$n=2^{\alpha}\cdot p_1^{\beta_1}\cdots p_k^{\beta_k}\cdot q_1^{\gamma_1}\cdots q_{\ell}^{\gamma_{\ell}}$, where the $p_i$ are the prime factors that are congruent to 1 (mod 4) and the $q_j$ are the
primes congruent to 3 (mod 4).
Then $n$ may be written as the sum of two squares (of integers, of course) if and only if all of the
exponents $\gamma_1, \ldots, \gamma_{\ell}$ are even.

(Hint:  Combine Theorems~\ref{squaremodq}, \ref{squaremodp}, and \ref{foil}.)
\end{theorem}\vskip20pt

\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\; \pmod{m_1} \\
& \vdots & \\
x & \equiv & a_r\; \pmod{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}

%\vspace{30pt}
%\hspace{2.5in}
%\copyright  {\tt 2010 Tom Church (based on script by John Boller)}

\end{document}