\documentclass{book}
%\documentstyle[amssymb,amsmath]{article}
%\usepackage{latexsym}
%\usepackage{amssymb,amsmath}
\usepackage{custom}

\addtolength{\evensidemargin}{-.5in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\textwidth}{1.4in}
\addtolength{\textheight}{1.4in}
\addtolength{\topmargin}{-.5in}

\pagestyle{empty}

\begin{document}

\begin{center}
\Large
Elementary Number Theory \\
Math 17500, Section 30 \\
Autumn Quarter 2008 \\
John Boller, e-mail:  {\tt boller@math.uchicago.edu} \\
website:  {\tt http://www.math.uchicago.edu/$\sim$boller/M175} \\
\end{center}


\vspace{50pt}
\LARGE
\begin{center}
{\bf Congruence in the Integers}
\end{center}

%\addtosection{1}
\vspace{30pt}
\normalsize
\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\;\mbox{(mod $n$)}$ provided that $n\,|\,(b-a)$.
\end{definition}

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

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

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

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

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

\begin{theorem}
If $a\equiv b\;\mbox{(mod $n$)}$, then $ac\equiv bc\;\mbox{(mod $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\;\mbox{(mod $n$)}$.
\end{theorem}

\begin{theorem}
Given $c\in\Z$, if $(a, n)=1$, 
then the congruence $ax\equiv c\;\mbox{(mod $n$)}$ has a solution for $x$ in 
the integers.
\end{theorem}

\begin{exercise}  Solve the following congruences for $x$:
\begin{exerenm}
\item  $3x\equiv 1\;\mbox{(mod 7)}$

\item  $8x\equiv 11\;\mbox{(mod 19)}$

\item  $25x+1\equiv 0\;\mbox{(mod 127)}$

\item  $22x\equiv 4\;\mbox{(mod 94)}$
\end{exerenm}
\end{exercise}

\begin{theorem}
If $m=(a, n)$, then 
$ax\equiv ay\;\mbox{(mod $n$)}$ 
if and only if 
$x\equiv y\;\mbox{(mod $\frac{n}{m}$)}$.
\end{theorem}

\begin{definition}  
If $a\equiv x\;\mbox{(mod $n$)}$, then $x$ is called a {\em residue of $a$ (mod $n$)}.  
\end{definition}

\begin{definition}  
A set of integers $\{x_1, \ldots, x_n\}$ is called a {\em complete residue system (mod $n$)} if, for
every $a\in\Z$, there is exactly one $x_i$ such that $a\equiv x_i\;\mbox{(mod $n$)}$.
\end{definition}

\begin{exercise}
Show that a complete residue system (mod $n$) must, in fact, have $n$ elements.
\end{exercise}

\begin{definition}  
A set of integers $\{x_1, \ldots, x_j\}$ is called a {\em reduced residue system (mod $n$)} if, for
every $a\in\Z$ such that $(a,n)=1$, 
there is exactly one $x_i$ such that $a\equiv x_i\;\mbox{(mod $n$)}$.
\end{definition}

\begin{exercise}
Find a reduced residue system (mod $n$) for $n=8, 10, 12, 20$.
\end{exercise}

\begin{definition}
If $n\in\Z$ and $n>0$, then {\em Euler's $\phi$-function} is denoted $\phi(n)$ and represents
the number of elements of a reduced residue system (mod $n$).
\end{definition}

\begin{exercise}
Show that $\phi(n)$ is the number of positive integers less than or equal to $n$ that are
relatively prime to $n$.
\end{exercise}

\begin{theorem}  
Let $n>0$ and suppose $(a,n)=1$.
Suppose $\{x_1, \ldots, x_{\phi(n)}\}$ is a reduced residue system (mod $n$). 
Then $\{ax_1, \ldots, ax_{\phi(n)}\}$ is also a reduced residue system (mod $n$).  
\end{theorem}

\begin{theorem}
If $n=ab$ and $(a,b)=1$, then $\phi(n)=\phi(a)\phi(b)$.
\end{theorem}

\begin{exercise}
Show that if $p$ is prime, then $\phi(p^n)=(p-1)p^{n-1}$.
\end{exercise}

\begin{exercise}
Let $n>1$, and let $P=\{p\in\Z\mid \mbox{$p$ is prime and $p|n$}\}$.
Show that
$$
\phi(n)=n\cdot\prod_{p\in P}\left(1-\frac{1}{p}\right).
$$
\end{exercise}

\begin{definition}
Fix $n>1$.
Let ${\mathbb Z}/n{\mathbb Z}=\{0, 1, 2, \ldots, n-1\}$.  (Note that
${\mathbb Z}/n{\mathbb Z}$ is a complete residue system mod $n$.)  Define
addition and multiplication in ${\mathbb Z}/n{\mathbb Z}$ as follows:
$$a+b=x\hspace{5pt}\mbox{where $x$ is the unique element of ${\mathbb Z}/n{\mathbb Z}$
such that $a+b\equiv x\;\mbox{(mod $n$)}$}$$
$$ab=x\hspace{5pt}\mbox{where $x$ is the unique element of ${\mathbb Z}/n{\mathbb Z}$
such that $ab\equiv x\;\mbox{(mod $n$)}$}$$
\end{definition}

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

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

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

\begin{exercise}
Fix $n>1$.  Show that if $R=\{x_1, \ldots, x_{\phi(n)}\}$ is a reduced residue system 
(mod $n$), then $R$ is a group under the law of composition:
$$
x_i * x_j = x_k
\hspace{5pt}\mbox{provided that $x_k$ is the unique element of $R$ such that
$x_ix_j\equiv x_k\;\mbox{(mod $n$)}$}
$$
\end{exercise}

\begin{theorem}
(Fermat's Little Theorem)  
If $p$ is prime and $a\in\Z$, then
$a^p\equiv a\; \mbox{(mod $p$)}$.
\end{theorem}

\begin{exercise}
If $p$ is prime and $a\in\Z$ with $p\not| \,a$, then
$a^{p-1}\equiv 1\; \mbox{(mod $p$)}$.
\end{exercise}

\begin{theorem}
(Euler's Generalization)
If $(a,n)=1$, then $a^{\phi(n)}\equiv 1\; \mbox{(mod $n$)}$.
\end{theorem}

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

\begin{theorem}
(Wilson's Theorem)  If $p$ is prime, then $(p-1)!\equiv -1\; \mbox{(mod $p$)}$.

(Hint:  It may be helpful to consider small primes such as $p=2$ and $p=3$ separately.)
\end{theorem}

\begin{theorem}
Let $p$ be prime.  Then the congruence
$x^2\equiv -1\; \mbox{(mod $p$)}$ has solutions 
if and only if $p=2$ or $p\equiv 1\; \mbox{(mod $4$)}$.
\end{theorem}

\begin{theorem}
Let $q$ be a prime factor of $a^2+b^2$. 
If $q\equiv 3\; \mbox{(mod $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}
Let $p$ be a prime such that $p\equiv 1\; \mbox{(mod $4$)}$.  Then there exist
integers $a, b$ such that $$p=a^2+b^2.$$
\end{theorem}

\noindent
For the following lemmas through Lemma 37, assume the following: 

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

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

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

\begin{lemma}
$|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\; \mbox{(mod $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\; \mbox{(mod $p$)}$ .
\end{lemma}

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

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

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

\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 primes 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 31, 32, and 38.)
\end{theorem}

\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}

%\vspace{30pt}
%\hspace{2.5in}
%\copyright  {\tt 2008 John Boller, University of Chicago}

%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%


\end{document}


