\documentclass[12pt,letterpaper]{book}
\usepackage{times}
\usepackage{amsthm}
\usepackage{makeidx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{hyperref}
\newcommand{\comment}[1]{}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{def1}{Definition}
\newtheorem{Def}{Definition}
\newtheorem{prop}{Proposition}
\newtheorem{remark}{Remark}
\newtheorem{notation}{Notation}
\newtheorem{example}{Example}
\newtheorem{conjecture}{Conjecture}
\newtheorem{examples}{Examples}
\linespread{1.3}
\title{An Introductory Course in Elementary Number Theory}
\author{Wissam Raji}
\date{}
\makeindex
\begin{document}
\maketitle
\begin{center}\textbf{Preface} \end{center}\par These notes serve as course notes for
an undergraduate course in number theory.  Most if not all
universities worldwide offer introductory courses in number theory
for math majors and in many cases as an elective course.

\par The notes contain a useful introduction to important topics that need to
be addressed in a course in number theory. Proofs of basic theorems
are presented in an interesting and comprehensive way that can be
read and understood even by non-majors with the exception in the
last three chapters where a background in analysis, measure theory
and abstract algebra is required. The exercises are carefully chosen
to broaden the understanding of the concepts.  Moreover, these notes
shed light on analytic number theory, a subject that is rarely seen
or approached by undergraduate students. One of the unique
characteristics of these notes is the careful choice of topics and
its importance in the theory of numbers. The freedom is given in the
last two chapters because of the advanced nature of the topics that
are presented.

Thanks to professor Pavel Guerzhoy from University of Hawaii for his
contribution in chapter 6 on continued fraction and to Professor
Ramez Maalouf from Notre Dame University, Lebanon for his
contribution to chapter 8.  \maketitle  \tableofcontents



\chapter{Introduction} Integers are the building blocks of the theory of
numbers. This chapter contains somewhat very simple and obvious
observations starting with properties of integers and yet the proofs
behind those observations are not as simple.  In this chapter we
introduce basic operations on integers and some algebraic
definitions that will be necessary to understand basic concepts in
this book.  We then introduce the Well ordering principle which
states basically that every set of positive integers has a smallest
element.  Proof by induction is also presented as an efficient
method for proving several theorems throughout the book. We proceed
to define the concept of divisibility and the division algorithm. We
then introduce the elementary but fundamental concept of a greatest
common divisor (gcd) of two integers, and the Euclidean algorithm
for finding the gcd of two integers. We end this chapter with Lame's
Lemma on an estimate of the number of steps in the Euclidean
algorithm needed to find the gcd of two integers.

\section{Algebraic Operations With Integers}
The set $\mathbb{Z}$ of all integers, which this book is all about,
consists of all positive and negative integers as well as 0. Thus
$\mathbb{Z}$ is the set given by
\begin{equation}
\mathbb{Z}=\{...,-4,-3,-2,-1,0,1,2,3,4,...\}.
\end{equation}
While the set of all {\it positive} integers, denoted by $\mathbb{N}$, is defined by
\begin{equation}
\mathbb{N}=\{1,2,3,4,...\}.
\end{equation}

On $\mathbb{Z}$, there are two basic binary operations, namely {\bf addition}  (denoted by $+$) and {\bf multiplication} (denoted by $\cdot$),
that satisfy some basic properties from which every other property for $\mathbb{Z}$ emerges.\\

\begin{enumerate}
\index{Commutativity}
\item \textbf{The Commutativity property for addition and multiplication}
\begin{eqnarray*}
a+b=b+a\\
a\cdot b=b\cdot a
\end{eqnarray*}\index{Associativity}
\item \textbf{Associativity property for addition and multiplication}
\begin{eqnarray*}
(a+b)+c&=&a+(b+c)\\
(a\cdot b)\cdot c&=& a\cdot (b\cdot c)
\end{eqnarray*}\index{Distributivity}
\item \textbf{The distributivity property of multiplication over addition}
\begin{eqnarray*}
a\cdot (b+c)&=&a\cdot b+a\cdot c.
\end{eqnarray*}
\end{enumerate}
\index{Identity Elements} In the set $\mathbb{Z}$ there are
"identity elements" for the two operations $+$ and $\cdot$, and
these are the elements $0$ and $1$ respectively, that satisfy the
basic properties
\begin{eqnarray*}
a + 0 =0+a=a\\
a\cdot 1 = 1\cdot a=a
\end{eqnarray*}
for every $a\in\mathbb{Z}$.\\

The set $\mathbb{Z}$ allows {\bf additive inverses} for its
elements, in the sense that for every $a\in\mathbb{Z}$ there exists
another integer in $\mathbb{Z}$, denoted by $-a$, such that
\begin{equation}
a+(-a)=0.
\end{equation}
While for multiplication, only the integer 1 has a {\bf
multiplicative inverse} in the sense that 1 is the only integer $a$
such that there exists another integer, denoted by $a^{-1}$ or by
$1/a$, (namely 1 itself in this case) such that
\begin{equation}
a\cdot a^{-1}=1.
\end{equation}

From the operations of addition and multiplication one can define
two other operations on $\mathbb{Z}$, namely {\bf subtraction}
(denoted by $-$) and {\bf division} (denoted by $/$). Subtraction is
a binary operation on $\mathbb{Z}$, i.e. defined for any two
integers in $\mathbb{Z}$, while division is not a binary operation
and thus is defined only for some specific couple of integers in
$\mathbb{Z}$. Subtraction and division are defined as follows:
\begin{enumerate}

\item $a-b$ is defined by $a+(-b)$, i.e. $a-b=a+(-b)$ for every $a,b\in\mathbb{Z}$
\item $a/b$ is defined by the integer $c$ if and only if $a=b\cdot c$.

\end{enumerate}


\section{The Well Ordering Principle and Mathematical Induction}
In this section, we present three basic tools that will often be used in proving properties of the integers. We start with a very important property of
integers called the well ordering principle. We then state what is known as the pigeonhole principle, and then we proceed to present an
important method called mathematical induction. \\
\\
\subsection{\textbf{The Well Ordering Principle}}

\textbf{The Well Ordering Principle:} \index{Well Ordering Principle} A least element exist in any non empty set of positive integers.\\

This principle can be taken as an axiom on integers and it will be
the key to proving many theorems.  As a result, we see that any set of
positive integers is well ordered while the set of all integers
is not well ordered.\\
\index{Proof by Contradiction}
\subsection{\textbf{The Pigeonhole Principle}}

\textbf{The Pigeonhole Principle:} \index{Pigeonhole Principle} If
$s$ objects are placed in $k$ boxes for $s>k$, then at least one box
contains more than one object.

\begin{proof}
Suppose that none of the boxes contains more than one object.  Then
there are at most $k$ objects.  This leads to a contradiction with
the fact that there are $s$ objects for $s>k$.
\end{proof}

\subsection{\textbf{The Principle of Mathematical Induction}}

\par We now present a valuable tool for proving results about
integers.  This tool is the principle of mathematical induction
\index{Mathematical Induction}.

\begin{theorem}
\textbf{The First Principle of Mathematical Induction:}  If a set of
positive integers has the property that, if it contains the integer
$k$, then it also contains $k+1$, and if this set contains 1 then it
must be the set of all positive integers. More generally, a property
concerning the positive integers that is true for $n=1$, and that is
true for the integer $n+1$ whenever it is true for the integer $n$,
must be true for all positive integers.
\end{theorem}

We use the well ordering principle to prove the first principle of
mathematical induction

\begin{proof}
Let $S$ be the set of positive integers containing the integer 1,
and the integer $k+1$ whenever it contains $k$.  Assume also that
$S$ is not the set of all positive integers.  As a result, there are
some integers that are not contained in $S$ and thus those integers
must have a least element $\alpha$ by the well ordering principle.
Notice that $\alpha \neq 1$ since $1\in S$. But $\alpha-1 \in S$ and
thus using the property of $S$, $\alpha \in S$.  Thus $S$ must
contain all positive integers.
\end{proof}

 We now present some examples in which we use the principle of
induction.

\begin{example}
Use mathematical induction to show that $\forall n\in \mathbb{N}$
\begin{equation}
\sum_{j=1}^nj=\frac{n(n+1)}{2}.
\end{equation}
\end{example}
\par First note that
\begin{equation*}
\sum_{j=1}^1j=1=\frac{1\cdot 2}{2}
\end{equation*}
and thus the the statement is true for $n=1$. For the remaining inductive step, suppose that the formula holds for
$n$, that is $\sum_{j=1}^nj=\frac{n(n+1)}{2}$.  We show
that
\begin{equation*}
\sum_{j=1}^{n+1}j=\frac{(n+1)(n+2)}{2}.
\end{equation*}
to complete the proof by induction. Indeed
\begin{equation*}
\sum_{j=1}^{n+1}j=\sum_{j=1}^nj+(n+1)=\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2},
\end{equation*}
and the result follows. \index{Proof by Induction}
\begin{example}
Use mathematical induction to prove that $n!\leq n^n$ for all
positive integers $n$.\\
\end{example}
\par Note that $1!=1\leq 1^1=1$.  We now present the inductive
step.  Suppose that
\begin{equation*}
n!\leq n^n
\end{equation*}
for some $n$, we prove that $(n+1)!\leq (n+1)^{n+1}$. Note that
\begin{equation*}
(n+1)!=(n+1)n!\leq (n+1).n^n<(n+1)(n+1)^{n}=(n+1)^{n+1}.
\end{equation*}
This completes the proof.

\begin{theorem}
\textbf{The Second Principle of Mathematical Induction:} A set of
positive integers that has the property that for every integer $k$,
if it contains all the integers 1 through $k$ then it contains $k+1$
and if it contains 1 then it must be the set of all positive
integers. More generally, a property concerning the positive
integers that is true for $n=1$, and that is true for all integers
up to $n+1$ whenever it is true for all integers up to $n$, must be
true for all positive integers.
\end{theorem} \index{Strong Induction}
\par The second principle of induction is also known as {\bf{the principle
of strong induction}}.  Also, the first principle of induction is
known as {\bf{the principle of weak induction}}.
\par To prove the second principle of induction, we use the first
principle of induction.
\begin{proof}
Let $T$ be a set of integers containing 1 and such that for every
positive integer $k$, if it contains $1,2,...,k$, then it contains
$k+1$.  Let $S$ be the set of all positive integers $k$ such that
all the positive integers less than or equal to $k$ are in $T$. Then
1 is in $S$, and we also see that $k+1$ is in $S$.  Thus $S$ must be
the set of all positive integers.  Thus $T$ must be the set of all
positive integers since $S$ is a subset of $T$.
\end{proof}

\textbf{Exercises}

\begin{enumerate}
\item{Prove using mathematical induction that $n<3^n$ for all
positive integers $n$.} \item{Show that
$\sum_{j=1}^nj^2=\frac{n(n+1)(2n+1)}{6}$}. \item{Use mathematical
induction to prove that
$\sum_{j=1}^n(-1)^{j-1}j^2=(-1)^{n-1}n(n+1)/2$.} \item{Use
mathematical induction to prove that $\sum_{j=1}^nj^3=[n(n+1)/2]^2$
for every positive integer $n$.}\item{Use mathematical induction to
prove that $\sum_{j=1}^n(2j-1)=n^2$}\item{Use mathematical induction
to prove that $2^n<n!$ for $n\geq 4$.}\item{Use mathematical
induction to prove that $n^2<n!$ for $n\geq 4$.}
\end{enumerate}



\section{Divisibility and the Division Algorithm}

We now discuss the concept of divisibility and its properties.

\subsection{Integer Divisibility}
\index{Divisibility}
\begin{definition}
If $a$ and $b$ are integers such that $a\neq 0$, then we say "$a$
divides $b$" if there exists an integer $k$ such that $b=ka$.
\end{definition}
\index{factor} \index{Multiple} If $a$ divides $b$, we also say "$a$
is a factor of $b$" or "$b$ is a multiple of $a$" and we write
$a\mid b$. If $a$ doesn't divide $b$, we write $a\nmid b$. For
example $2\mid 4$ and $7\mid 63$, while $5\nmid 26$.

\begin{example}
a) Note that any even integer has the form $2k$ for some integer $k$, while any odd integer has the form $2k+1$ for some integer $k$. Thus $2|n$ if $n$ is even,
while $2\nmid n$ if $n$ is odd.\\
b) $\forall a\in\mathbb{Z}$ one has that $a\mid 0$.\\
c) If $b\in\mathbb{Z}$ is such that $|b|<a$, and $b\neq 0$, then $a\nmid b$.
\end{example}

\begin{theorem}
If $a, b$ and $c$ are integers such that $a\mid b$ and $b\mid c$,
then $a\mid c$.
\end{theorem}

\begin{proof}
Since $a\mid b$ and $b\mid c$, then there exist integers $k_1$ and
$k_2$ such that $b=k_1a$ and $c=k_2b$.  As a result, we have
$c=k_1k_2a$ and hence $a\mid c$.
\end{proof}

\begin{example}
Since $6\mid 18$ and $18\mid 36$, then $6\mid 36$.
\end{example}

The following theorem states that if an integer divides two other
integers then it divides any linear combination of these integers.

\begin{theorem}\label{thm4}
If $a,b,c,m$ and $n$ are integers, and if $c\mid a$ and $c\mid b$,
then $c\mid (ma+nb)$.
\end{theorem}

\begin{proof}
Since $c\mid a$ and $c\mid b$, then by definition there exists $k_1$
and $k_2$ such that $a=k_1c$ and $b=k_2c$. Thus
\begin{equation*}
ma+nb=mk_1c+nk_2c=c(mk_1+nk_2),
\end{equation*}
and hence $c\mid (ma+nb)$.
\end{proof}

Theorem \ref{thm4} can be generalized to any finite linear combination as follows. If\\
\begin{equation*}
a\mid b_1, a\mid b_2,...,a\mid b_n
\end{equation*}
then
\begin{equation}
a\mid \sum_{j=1}^nk_jb_j
\end{equation}
for any set of integers $k_1,\cdots,k_n\in\mathbb{Z}$. It would be a
nice exercise to prove the generalization by induction.

\subsection{The Division Algorithm}

\par The following theorem states somewhat an elementary but very useful
result.

\begin{theorem}\label{thm5}\textbf{The Division Algorithm} \index{Division Algorithm} If $a$ and $b$ are
integers such that $b>0$, then there exist unique integers $q$ and
$r$ such that $a=bq+r$ where $0\leq r< b$.
\end{theorem}

\begin{proof}
Consider the set $A=\{a-bk\geq 0 \mid k\in \mathbb{Z}\}$.  Note that
$A$ is nonempty since for $k<a/b$, $a-bk>0$.  By the well ordering
principle, $A$ has a least element $r=a-bq$ for some $q$. Notice
that $r\geq 0$ by construction.  Now if  $r\geq b$ then (since
$b>0$)
\begin{equation*}
r>r-b=a-bq-b=a-b(q+1)=\geq 0.
\end{equation*}
This leads to a contradiction since $r$ is assumed to be the least
positive integer of the form $r=a-bq$.  As a result we have $0\leq r
<b$.
\par We will show that $q$ and $r$ are unique.  Suppose
that $a=bq_1+r_1$ and $a=bq_2+r_2$ with $0\leq r_1<b$ and $0\leq
r_2<b$.  Then we have
\begin{equation*}
b(q_1-q_2)+(r_1-r_2)=0.
\end{equation*}
As a result we have
\begin{equation*}
b(q_1-q_2)=r_2-r_1.
\end{equation*}
Thus we get that
\begin{equation*}
b\mid (r_2-r_1).
\end{equation*}
And since $-\max(r_1,r_2)\leq|r_2-r_1|\leq\max(r_1,r_2)$, and $b>\max(r_1,r_2)$,
then $r_2-r_1$ must be $0$, i.e. $r_2=r_1$. And since
$bq_1+r_1=bq_2+r_2$, we also get that $q_1=q_2$. This proves uniqueness.
\end{proof}

\begin{example}
If $a=71$ and $b=6$, then $71=6\cdot 11+5$.  Here $q=11$ and $r=5$.
\end{example}

\textbf{Exercises}
\begin{enumerate}
\item{Show that $5\mid 25, 19\mid38$ and $2\mid 98$.}\item{Use the
division algorithm to find the quotient and the remainder when 76 is
divided by 13}. \item{Use the division algorithm to find the
quotient and the remainder when -100 is divided by 13.}\item{Show
that if $a,b,c$ and $d$ are integers with $a$ and $c$ nonzero, such
that $a\mid b$ and $c\mid d$, then $ac\mid bd$.}\item{Show that if
$a$ and $b$ are positive integers and $a\mid b$, then $a\leq
b$.}\item{Prove that the sum of two even integers is even, the sum
of two odd integers is even and the sum of an even integer and an
odd integer is odd.}\item{Show that the product of two even integers
is even, the product of two odd integers is odd and the product of
an even integer and an odd integer is even.} \item{Show that if $m$
is an integer then $3$ divides $m^3-m$.} \item{Show that the square
of every odd integer is of the form $8m+1$.}\item{Show that the
square of any integer is of the form $3m$ or $3m+1$ but not of the
form $3m+2$.}\item{Show that if $ac\mid bc$, then $a\mid
b$.}\item{Show that if $a\mid b$ and $b\mid a$ then $a=\pm b$.}
\end{enumerate}




\section{Representations of Integers in Different Bases}
In this section, we show how any positive integer can be written in
terms of any positive base integer expansion in a unique way.
Normally we use decimal notation to represent integers, we will show
how to convert an integer from decimal notation into any other
positive base integer notation and vise versa.  Using the decimal
notation in daily life is simply better because we have ten fingers
which \index{Decimal Notation}
facilitates all the mathematical operations. \\
\index{Base Expansion} \textbf{Notation} An integer $a$ written in
base $b$ expansion is denoted by $(a)_b$.

\begin{theorem}
Let $b$ be a positive integer with $b>1$.  Then any positive integer
$m$ can be written uniquely as
\begin{equation*}
m=a_lb^l+a_{l-1}b^{l-1}+...+a_1b+a_0,
\end{equation*}
where $l$ is a positive integer, $0\leq a_j<b$ for $j=0,1,...,l$ and
$a_l\neq 0$.
\end{theorem}
\begin{proof}
We start by dividing $m$ by $b$ and we get
\begin{equation*}
m=bq_0+a_0, \ \ \ 0\leq a_0 <b.
\end{equation*}
If $q_0\neq 0$ then we continue to divide $q_0$ by $b$ and we get
\begin{equation*}
q_0=bq_1+a_1, \ \ \ 0\leq a_1<b.
\end{equation*}
We continue this process and hence we get
\begin{eqnarray*}
q_1&=&bq_2+a_2, \ \ \  0\leq a_2<b,\\
&.&\\
&.&\\
&.&\\
q_{l-2}&=&bq_{l-1}+a_{l-1}, \ \ \ 0\leq a_{l-1}<b,\\
q_{l-1}&=&b\cdot 0+a_l, \ \ \ 0\leq a_l<b.
\end{eqnarray*}
Note that the sequence $q_0,q_1,...$ is a decreasing sequence of
positive integers with a last term $q_l$ that must be 0.
\par Now substituting the equation $q_0=bq_1+a_1$ in $m=bq_0+a_0$, we get
\begin{equation*}
m=b(bq_1+a_1)+a_0=b^2q_1+a_1b+a_0,
\end{equation*}
Successively substituting the equations in $m$, we get
\begin{eqnarray*}
m&=&b^3q_2+a_2b^2+a_1b+a_0,\\
&.&\\
&.&\\
&.&\\
&=&b^lq_{l-1}+a_{l-1}b^{l-1}+...+a_1b+a_0,\\
&=& a_lb^l+a_{l-1}b^{l-1}+...+a_1b+a_0.
\end{eqnarray*}
What remains to prove is that the representation is unique. Suppose
now that
\begin{equation*}
m=a_lb^l+a_{l-1}b^{l-1}+...+a_1b+a_0=c_lb^l+c_{l-1}b^{l-1}+...+c_1b+c_0
\end{equation*}
where if the number of terms is different in one expansion, we add
zero coefficients to make the number of terms agree.  Subtracting
the two expansions, we get
\begin{equation*}
(a_l-c_l)b^l+(a_{l-1}-c_{l-1})b^{l-1}+...+(a_1-c_1)b+(a_0-c_0)=0.
\end{equation*}
If the two expansions are different, then there exists $0\leq j\leq
l$ such that $c_j\neq a_j$.  As a result, we get
\begin{equation*}
b^j((a_l-c_l)b^{l-j}+...+(a_{j+1}-c_{j+1})b+(a_j-c_j))=0
\end{equation*}
and since $b\neq 0$, we get
\begin{equation*}
(a_l-c_l)b^{l-j}+...+(a_{j+1}-c_{j+1})b+(a_j-c_j)=0.
\end{equation*}
We now get
\begin{equation*}
 a_j-c_j=(a_l-c_l)b^{l-j}+...+(a_{j+1}-c_{j+1})b,
\end{equation*}
and as a result, $b\mid (a_j-c_j)$.  Since $0\leq a_j<b$ and $0\leq
c_j<b$, we get that $a_j=c_j$.  This is a contradiction and hence
the expansion is unique.
\end{proof}
\index{Binary Representation} Note that base 2 representation of
integers is called binary representation.  Binary representation
plays a crucial role in computers.  Arithmetic operations can be
carried out on integers with any positive integer base but it will
not be addressed in this book. We now present examples of how to
convert from decimal integer representation to any other base
representation and vise versa.
\begin{example}
To find the expansion of 214 base 3:
\end{example}
we do the following
\begin{eqnarray*}
214&=&3\cdot 71+1\\
71&=& 3\cdot 23+2\\
23&=& 3\cdot 7+2\\
7&=& 3\cdot 2+1\\
2&=& 3\cdot 0+2\\
\end{eqnarray*}
As a result, to obtain a base 3 expansion of 214, we take the
remainders of divisions and we get that $(214)_{10}=(21221)_3$.


\begin{example}
To find the base 10 expansion, i.e. the decimal expansion, of $(364)_7$:
\end{example}
We do the following: $4\cdot 7^0+6\cdot 7^1+3\cdot 7^2=4+42+147=193$.

In some cases where base $b>10$ expansion is needed, we
add some characters to represent numbers greater than 9.  It is
known to use the alphabetic letters to denote integers greater than
9 in base b expansion for $b>10$. For example $(46BC29)_{13}$ where
$A=10, B=11, C=12$.
\par To convert from one base to the other, the simplest way is to
go through base 10 and then convert to the other base.  There are
methods that simplify conversion from one base to the other but it
will not be addressed in this book.\\

\textbf{Exercises}
\begin{enumerate}
\item{Convert $(7482)_{10}$ to base 6 notation.} \item{Convert
$(98156)_{10}$ to base 8 notation.}\item{Convert $(101011101)_2$ to
decimal notation.}\item{Convert $(AB6C7D)_{16}$ to decimal
notation.}\item{Convert $(9A0B)_{16}$ to binary notation.}
\end{enumerate}


\section{The Greatest Common Divisor}
\par  In this section we define the greatest
common divisor (gcd) \index{Greatest Common Divisor} of two integers
and discuss its properties. We also prove that the greatest common
divisor of two integers is a linear combination of these integers.

Two integers $a$ and $b$, not both $0$, can have only finitely many
divisors, and thus can have only finitely many common divisors. In
this section, we are interested in the greatest common divisor of
$a$ and $b$. Note that the divisors of $a$ and that of $\mid a \mid
$ are the same.

\begin{definition}
The greatest common divisor of two integers $a$ and $b$ is the
greatest integer that divides both $a$ and $b$.
\end{definition}

We denote the greatest common divisor of two integers $a$ and $b$ by
$(a,b)$.  We also define $(0,0)=0$.

\begin{example}
Note that the greatest common divisor of 24 and 18 is 6.  In other
words $(24,18)=6$.
\end{example}

There are couples of integers (e.g. 3 and 4, etc...) whose greatest
common divisor is 1 so we call such integers relatively prime
integers.\index{Relatively Prime}

\begin{definition}
Two integers $a$ and $b$ are relatively prime if $(a,b)=1$.
\end{definition}

\begin{example}
The greatest common divisor of 9 and 16 is 1, thus they are
relatively prime.
\end{example}

Note that every integer has positive and negative divisors.  If
$a$ is a positive divisor of $m$, then $-a$ is also a divisor of
$m$.  Therefore by our definition of the greatest common divisor, we
can see that $(a,b)=(\mid a\mid, \mid b\mid)$.

\par We now present a theorem about the greatest common divisor of
two integers.  The theorem states that if we divide two integers by
their greatest common divisor, then the outcome is a couple of integers that are relatively prime.

\begin{theorem}
If $(a,b)=d$ then $(a/d,b/d)=1$.
\end{theorem}

\begin{proof}
We will show that $a/d$ and $b/d$ have no common positive divisors
other than $1$.  Assume that $k$ is a positive common divisor such
that $k\mid a/d$ and $k\mid b/d$.  As a result, there are two
positive integers $m$ and $n$ such that
\begin{equation*}
a/d=km \hspace{0.3 cm}\mbox{and} \ \  b/d=kn
\end{equation*}
Thus we get that
\begin{equation*}
a=kmd \hspace{0.3 cm}\mbox{and} \ \  b=knd.
\end{equation*}
Hence $kd$ is a common divisor of both $a$ and $b$.  Also,
$kd\geq d$. However, $d$ is the greatest common divisor of $a$ and
$b$.  As a result, we get that $k=1$.
\end{proof}

The next theorem shows that the greatest common divisor of two
integers does not change when we add a multiple of one of the
two integers to the other.

\begin{theorem}
Let $a,b$ and $c$ be integers.  Then $(a,b)=(a+cb,b)$.
\end{theorem}

\begin{proof}
We will show that every divisor of $a$ and $b$ is also a divisor of
$a+cb$ and $b$ and vise versa.  Hence they have exactly the same
divisors.  So we get that the greatest common divisor of $a$ and $b$
will also be the greatest common divisor of $a+cb$ and $b$. Let $k$
be a common divisor of $a$ and $b$. By Theorem \ref{thm4},  $k \mid
(a+cb)$ and hence $k$ is a divisor of $a+cb$.  Now assume that $l$
is a common divisor of $a+cb$ and $b$. Also by Theorem \ref{thm4} we
have ,
\begin{equation*}
l\mid ((a+cb)-cb)=a.
\end{equation*}
As a result, $l$ is a common divisor of $a$ and $b$ and the result
follows.
\end{proof}

\begin{example}
Notice that $(4,14)=(4,14-3\cdot 4)=(4,2)=2$.
\end{example}

We now present a theorem which proves that the greatest common
divisor of two integers can be written as a linear combination of
the two integers.

\begin{theorem}\label{thm9}
The greatest common divisor of two integers $a$ and $b$, not both
$0$ is the least positive integer such that $ma+nb=d$ for some
integers $m$ and $n$.
\end{theorem}

\begin{proof}  Assume without loss of generality that $a$ and $b$ are positive integers.
Consider the set of all positive integer linear combinations of $a$
and $b$. This set is non empty since $a=1\cdot a+0\cdot b$ and $b=0\cdot a+1\cdot b$ are both
in this set. Thus this set has a least element $d$ by the
well-ordering principle. Thus $d=ma+nb$ for some integers $m$ and
$n$.  We have to prove that $d$ divides both $a$ and $b$ and that it
is the greatest divisor of $a$ and $b$.
\par By the division algorithm, we have
\begin{equation*}
a=dq+r, \ \ \ 0\leq r<d.
\end{equation*}
Thus we have
\begin{equation*}
r=a-dq=a-q(ma+nb)=(1-qm)a-qnb.
\end{equation*}
We then have that $r$  is a linear combination of $a$ and $b$. Since
$0\leq r<d$ and $d$ is the least positive integer which is a linear
combination of $a$ and $b$, then $r=0$ and $a=dq$.  Hence $d\mid
a$.  Similarly $d\mid b$.  Now notice that if there is a divisor $c$
that divides both $a$ and $b$.  Then $c$ divides any linear
combination of $a$ and $b$ by Theorem 4.  Hence $c\mid d$. This
proves that any common divisor of $a$ and $b$ divides $d$. Hence
$c\leq d$, and $d$ is the greatest divisor.
\end{proof}

As a result, we conclude that if $(a,b)=1$ then there exist integers
$m$ and $n$ such that $ma+nb=1$.


\begin{definition}
Let $a_1,a_2,...,a_n$ be integers, not all $0$.  The greatest common
divisor of these integers is the largest integer that divides all of
the integers in the set.  The greatest common divisor of
$a_1,a_2,...,a_n$ is denoted by      $(a_1,a_2,...,a_n)$.
\end{definition}
\index{Mutually Relatively Prime}
\begin{definition}
The integers $a_1,a_2,...,a_n$ are said to be mutually relatively
prime if $(a_1,a_2,...,a_n)=1$.
\end{definition}

\begin{example}
The integers $3, 6, 7$ are mutually relatively prime since
$(3,6,7)=1$ although $(3,6)=3$.
\end{example}
\index{Pairwise Prime}
\begin{definition}
The integers $a_1,a_2,...,a_n$ are called pairwise prime
if for each $i\neq j$, we have $(a_i,a_j)=1$.
\end{definition}

\begin{example}
The integers $3,14,25$ are pairwise relatively prime.  Notice also
that these integers are mutually relatively prime.
\end{example}

\par Notice that if $a_1,a_2,...,a_n$ are pairwise relatively prime then they are mutually relatively prime.
\\
\\
\\
\\
\textbf{Exercises}
\begin{enumerate}
\item{Find the greatest common divisor of 15 and 35.} \item{Find
the greatest common divisor of 100 and 104.} \item{Find the greatest
common divisor of -30 and 95.}\item{Let $m$ be a positive integer.
Find the greatest common divisor of $m$ and $m+1$.}\item{Let $m$ be
a positive integer, find the greatest common divisor of $m$ and
$m+2$.} \item{Show that if $m$ and $n$ are integers such that
$(m,n)=1$, then (m+n,m-n)=1 or 2.}\item{Show that if $m$ is a
positive integer, then $3m+2$ and $5m+3$ are relatively
prime.}\item{Show that if $a$ and $b$ are relatively prime integers,
then $(a+2b,2a+b)=1$or $3$.} \item{Show that if $a_1,a_2,...,a_n$
are integers that are not all 0 and $c$ is a positive integer, then
$(ca_1,ca_2,...,ca_n)=c(a_1,a_2,...a_n).$}
\end{enumerate}

\section{The Euclidean Algorithm} \index{Euclidean Algorithm}
In this section we describe a systematic method that determines the
greatest common divisor of two integers. This method is called the
Euclidean algorithm.
\begin{lemma}\label{lem1}
If $a$ and $b$ are two integers and $a=bq+r$ where also $q$ and $r$
are integers, then $(a,b)=(r,b)$.
\end{lemma}

\begin{proof}
Note that by theorem 8, we have $(bq+r,b)=(b,r)$.
\end{proof}
The above lemma will lead to a more general version of it.  We now
present the Euclidean algorithm in its general form.  It states that
the greatest common divisor of two integers is the last non zero
remainder of the successive division. \index{Division Algorithm}
\begin{theorem}
Let $a=r_0$ and $b=r_1$ be two positive integers where $a\geq b$. If
we apply the division algorithm successively to obtain that
\begin{equation*}
r_j=r_{j+1}q_{j+1}+r_{j+2} \ \ \mbox{where} \ \  0\leq
r_{j+2}<r_{j+1}
\end{equation*}
for all $j=0,1,...,n-2$ and
\begin{equation*}
r_{n+1}=0.
\end{equation*}
Then $(a,b)=r_{n}$.
\end{theorem}

\begin{proof}
By applying the division algorithm, we see that
\begin{eqnarray*}
r_0&=&r_1q_1+r_2 \ \ \ \ \ 0\leq r_2<r_1, \\
r_1&=&r_2q_2+r_3 \ \ \ \ \ 0\leq r_3<r_2, \\
 &.&    \\
 &.&    \\
&.&    \\
r_{n-2}&=&r_{n-1}q_{n-1}+r_{n} \ \ \ \ \ 0\leq r_{n}<r_{n-1}, \\
r_{n-1}&=&r_{n}q_{n}.
\end{eqnarray*}
Notice that, we will have a remainder of $0$ eventually since all
the remainders are integers and every remainder in the next step is
less than the remainder in the previous one.  By Lemma \ref{lem1},
we see that
\begin{equation*}
(a,b)=(b,r_2)=(r_2,r_3)=...=(r_n,0)=r_n.
\end{equation*}
\end{proof}

\begin{example}
We will find the greatest common divisor of $4147$ and $10672$:\\
\end{example}
Note that
\begin{eqnarray*}
 10672&=&4147\cdot 2+2378,\\
 4147&=&2378\cdot 1+1769,\\
2378&=&1769\cdot 1+609,\\
1769&=&609\cdot 2 +551,\\
609&=& 551\cdot 1+58, \\
551&=&58\cdot 9+ 29,\\
 58&=&29\cdot 2,\\
\end{eqnarray*}
Hence $(4147,10672)=29.$


We now use the steps in the Euclidean algorithm to write the
greatest common divisor of two integers as a linear combination of
the two integers.  The following example will actually determine the
variables $m$ and $n$ described in Theorem \ref{thm9}.  The
following algorithm can be described by a general form but for the
sake of simplicity of expressions we will present an example that
shows the steps for obtaining the greatest common divisor of two
integers as a linear combination of the two integers.

\begin{example}
Express 29 as a linear combination of $4147$ and $10672$:\\
\end{example}
\begin{eqnarray*}
29&=&551-9\cdot 58,\\
  &=& 551-9(609-551\cdot 1),\\
  &=& 10.551-9.609,\\
  &=& 10\cdot (1769-609\cdot 2)-9\cdot 609,\\
  &=& 10\cdot 1769-29\cdot 609,\\
  &=& 10\cdot 1769-29(2378-1769\cdot 1),\\
  &=& 39\cdot 1769-29\cdot 2378,\\
  &=& 39(4147-2378\cdot 1)-29\cdot 2378,\\
  &=& 39\cdot 4147-68\cdot 2378,\\
  &=& 39\cdot 4147-68(10672-4147\cdot 2),\\
  &=& 175\cdot 4147-68\cdot 10672,
\end{eqnarray*}
As a result, we see that $29=175\cdot 4147-68\cdot 10672$.

\textbf{Exercises}
\begin{enumerate}
\item{Use the Euclidean algorithm to find the greatest common
divisor of 412 and 32 and express it in terms of the two
integers.}\item{Use the Euclidean algorithm to find the greatest
common divisor of 780 and 150 and express it in terms of the two
integers.}\item{Find the greatest common divisor of $70,98,
108$.}\item{Let $a$ and $b$ be two positive even integers.  Prove
that $(a,b)=2(a/2,b/2).$}\item{Show that if $a$ and $b$ are positive
integers where $a$ is even and $b$ is odd, then $(a,b)=(a/2,b).$}
\end{enumerate}

\section{Lame's Theorem} \index{Lame's Theorem}
In this section, we give an estimate to the number of steps needed
to find the greatest common divisor of two integers using the
Euclidean algorithm.  To do this, we have to introduce the Fibonacci
numbers for the sake of proving a lemma that gives an estimate on
the growth of Fibonacci numbers in the Fibonacci sequence.  The
lemma that we prove will be used in the proof of Lame's theorem.
\index{Polynomials}
\begin{definition}
The Fibonacci sequence \index{Fibonacci Sequence}is defined
recursively by $f_1=1$, $f_2=1$, and
\begin{equation*}
f_{n}=f_{n-1}+f_{n-2} \mbox{for} \ \  n\geq 3.
\end{equation*}
The terms in the sequence are called Fibonacci numbers.
\end{definition}

In the following lemma, we give a lower bound on the growth of
Fibonacci numbers. We will show that Fibonacci numbers grow faster
than a geometric series with common ratio $\alpha=(1+\sqrt{5})/2$.

\begin{lemma}\label{lem2}
For $n\geq 3$, we have $f_n>\alpha^{n-2}$ where
$\alpha=(1+\sqrt{5})/2$.
\end{lemma}

\begin{proof}
We use the second principle of mathematical induction to prove our
result.  It is easy to see that this is true for $n=3$ and $n=4$.
Assume that $\alpha^{k-2}<f_k$ for all integers $k$ where $k\leq n$.
Now since $\alpha$ is a solution of the polynomial $x^2-x-1=0$, we
have $\alpha^2=\alpha+1$. Hence
\begin{equation*}
\alpha^{n-1}=\alpha^2.\alpha^{n-3}=(\alpha+1).\alpha^{n-3}=\alpha^{n-2}+\alpha^{n-3}.
\end{equation*}
By the inductive hypothesis, we have
\begin{equation*}
\alpha^{n-2}<f_n, \ \ \ \alpha^{n-3}<f_{n-1}.
\end{equation*}
After adding the two inequalities, we get
\begin{equation*}
\alpha^{n-1}<f_{n}+f_{n-1}=f_{n+1}.
\end{equation*}
\end{proof}
We now present Lame's theorem.

\begin{theorem}
using the Euclidean algorithm to find the greatest common divisor of
two positive integers  has number of divisions less than or equal
five times the number of decimal digits in the minimum of the two
integers.
\end{theorem}

\begin{proof}
Let $a$ and $b$ be two positive integers where $a>b$.  Applying the
Euclidean algorithm to find the greatest common divisor of two
integers with $a=r_0$ and $b=r_1$, we get
\begin{eqnarray*}
r_0&=&r_1q_1+r_2 \ \ \ \ \ 0\leq r_2<r_1, \\
r_1&=&r_2q_2+r_3 \ \ \ \ \ 0\leq r_3<r_2, \\
 &.&    \\
 &.&    \\
&.&    \\
r_{n-2}&=&r_{n-1}q_{n-1}+r_{n} \ \ \ \ \ 0\leq r_{n}<r_{n-1}, \\
r_{n-1}&=&r_{n}q_{n}.
\end{eqnarray*}
Notice that each of the quotients $q_1,q_2,...,q_{n-1}$ are all
greater than 1 and $q_n\geq 2$ and this is because $r_n<r_{n-1}$.
Thus we have
\begin{eqnarray*}
r_n&\geq& 1=f_2,\\
r_{n-1}&\geq& 2r_n\geq 2f_2=f_3,\\
r_{n-2}&\geq& r_{n-1}+r_n\geq f_3+f_2=f_4,\\
r_{n-3}&\geq& r_{n-2}+r_{n-1}\geq f_4+f_3=f_5,\\
&.&\\
&.&\\
&.&\\
r_2&\geq& r_3+r_4\geq f_{n-1}+f_{n-2}=f_n,\\
b&=& r_1\geq r_2+r_3\geq f_n+f_{n-1}=f_{n+1}.
\end{eqnarray*}
Thus notice that $b\geq f_{n+1}$.  By Lemma \ref{lem2}, we have
$f_{n+1}>\alpha^{n-1}$ for $n>2$.  As a result, we have
$b>\alpha^{n-1}$.  Now notice since
\begin{equation*}
\log_{10}\alpha>\frac{1}{5},
\end{equation*}
 we see that
\begin{equation*}
log_{10}b>(n-1)/5.
\end{equation*}
Thus we have
\begin{equation*}
n-1<5log_{10}b.
\end{equation*}
Now let $b$ has $k$ decimal digits. As a result, we have $b<10^k$
and thus $log_{10}b<k$. Hence we conclude that $n-1<5k$.  Since $k$
is an integer, we conclude that $n\leq 5k$.
\end{proof}

\textbf{Exercises}
\begin{enumerate}
\item{Find an upper bound for the number of steps in the Euclidean
algorithm that is used to find the greatest common divisor of
38472 and 957748838.}\\
\item{Find an upper bound for the number of steps in the Euclidean
algorithm that is used to find the greatest common divisor of 15 and
75.  Verify your result by using the Euclidean algorithm to find the
greatest common divisor of the two
integers.}\\
\end{enumerate}







\chapter{Prime Numbers}
Prime numbers, the building blocks of integers, have been studied
extensively over the centuries.  Being able to present an integer
uniquely as product of primes is the main reason behind the whole
theory of numbers and behind the interesting results in this theory.
Many interesting theorems, applications and conjectures have been
formulated based on the properties of prime numbers.
\par In this chapter, we present methods to determine whether a number
is prime or composite using an ancient Greek method invented by
Eratosthenes.  We also show that there are infinitely many prime
numbers. We then proceed to show that every integer can be written
uniquely as a product of primes.  \par We introduce as well the
concept of diophantine equations where integer solutions from given
equations are determined using the greatest common divisor. We then
mention the Prime Number theorem without giving a proof of course in
addition to other conjectures and major results related to prime
numbers.



\section{The Sieve of Eratosthenes}

\begin{definition} \index{Prime Numbers}
A prime is an integer greater than 1 that is only divisible by 1 and
itself.
\end{definition}

\begin{example}
The integers 2, 3, 5, 7, 11 are prime integers.
\end{example}

Note that any integer greater than 1 that is not prime is said to be a
\textit{composite} number.\\

We now present the sieve of Eratosthenes. \index{The Sieve of
Eratosthenes} The Sieve of Eratosthenes is an ancient method of
finding prime numbers up to a specified integer.  This method was
invented by the ancient Greek mathematician Eratosthenes. There are
several other methods used to determine whether a number is prime or
composite. We first present a lemma that will be needed in the proof
of several theorems.

\begin{lemma}
Every integer greater than one has a prime divisor.
\end{lemma}

\begin{proof}
We present the proof of this Lemma by contradiction.  Suppose that
there is an integer greater than one that has no prime divisors.
Since the set of integers with elements greater than one with no
prime divisors is nonempty, then by the well ordering principle
there is a least positive integer $n$ greater than one that has no
prime divisors.  Thus $n$ is composite since $n$ divides $n$. Hence
\begin{equation*}
n=ab \mbox{with}  \ \ 1<a<n \mbox{and} \ \  1<b<n.
\end{equation*}
Notice that $a<n$ and as a result since $n$ is minimal, $a$ must
have a prime divisor which will also be a divisor of $n$.
\end{proof}

\index{Composite Integers}
\begin{theorem}
If $n$ is a composite integer, then n has a prime factor not
exceeding $\sqrt{n}$.
\end{theorem}

\begin{proof}
Since $n$ is composite, then $n=ab$, where $a$ and $b$ are integers
with $1<a\leq b<n$.  Suppose now that $a>\sqrt{n}$, then
\begin{equation*}
\sqrt{n}<a \leq b
\end{equation*}
and as a result
\begin{equation*}
ab>\sqrt{n}\sqrt{n}=n.
\end{equation*}
Therefore $a\leq \sqrt{n}$. Also, by Lemma 3, $a$ must have a prime
divisor $a_1$ which is also a prime divisor of $n$ and thus this
divisor is less than $a_1 \leq a\leq \sqrt{n}$.
\end{proof}

We now present the algorithm of the Sieve of Eratosthenes that is
used to determine prime numbers up to a given integer.\\

\textbf{The Algorithm of the Sieve of Eratosthenes}
\begin{enumerate}
\item{Write a list of numbers from 2 to the largest number $n$ you
want to test. Note that every composite integer less than $n$ must
have a prime factor less than $\sqrt{n}$. Hence you need to strike
off the multiples of the primes that are less than $\sqrt{n}$}
 \item{Strike off all multiples of 2 greater than 2 from the list . The first remaining number
in the list is a prime number.} \item{Strike off all multiples of
this number from the list.} \item{Repeat the above steps until no
more multiples are found of the prime integers that are less than
$\sqrt{n}$}
\end{enumerate}

\textbf{Exercises}
\begin{enumerate}
\item{Use the Sieve of Eratosthenes to find all primes less than
100.} \item{Use the Sieve of Eratosthenes to find all primes less
than 200.}\item{Show that no integer of the form $a^3+1$ is a prime
except for $2=1^3+1$.}\item{Show that if $2^n-1$ is prime, then $n$
is prime.  \\Hint: Use the identity
$(a^{kl}-1)=(a^{k}-1)(a^{k(l-1)}+a^{k(l-2)}+...+a^k+1)$}.
\end{enumerate}


\section{The infinitude of Primes}
We now show that there are infinitely many primes.  There are
several ways to prove this result.  An alternative proof to the one
presented here is given as an exercise.  The proof we will provide
was presented by Euclid in his book the Elements.

\begin{theorem}
There are infinitely many primes.
\end{theorem}

\begin{proof}
We present the proof by contradiction.  Suppose there are finitely
many primes $p_1, p_2, ...,p_n$, where $n$ is a positive integer.
Consider the integer $Q$ such that
\begin{equation*}
Q=p_1p_2...p_n+1.
\end{equation*}
By Lemma 3, $Q$ has at least a prime divisor, say $q$.  If we prove
that $q$ is not one of the primes listed then we obtain a
contradiction.  Suppose now that $q=p_i$ for $1\leq i\leq n$. Thus
$q$ divides $p_1p_2...p_n$ and as a result $q$ divides
$Q-p_1p_2...p_n$.  Therefore $q$ divides 1.  But this is impossible
since there is no prime that divides 1 and as a result $q$ is not
one of the primes listed.
\end{proof}
The following theorem discusses the large gaps between primes.  It
simply states that there are arbitrary large gaps in the series of
primes and that the primes are spaced irregularly.

\begin{theorem}
Given any positive integer $n$, there exists $n$ consecutive
composite integers.
\end{theorem}

\begin{proof}
Consider the sequence of integers
\begin{equation*}
(n+1)!+2, (n+1)!+3,...,(n+1)!+n, (n+1)!+n+1
\end{equation*}
Notice that every integer in the above sequence is composite because
$k$ divides $(n+1)!+k$ if $2\leq k\leq n+1$ by \ref{thm4}.
\end{proof}

\textbf{Exercises}
\begin{enumerate}
\item{Show that the integer $Q_n=n!+1$, where $n$ is a positive
integer, has a prime divisor greater than $n$.  Conclude that there
are infinitely many primes.  Notice that this exercise is another
proof of the infinitude of primes.} \item{Find the smallest five
consecutive composite integers.}\item{Find one million consecutive
composite integers.}\item{Show that there are no prime triplets
other than 3,5,7.}
\end{enumerate}


\section{The Fundamental Theorem of Arithmetic}
The Fundamental Theorem of Arithmetic is one of the most important
results in this chapter. It simply says that every positive integer
can be written uniquely as a product of primes.  The unique
factorization is needed to establish much of what comes later. There
are systems where unique factorization fails to hold.  Many of these
examples come from algebraic number theory.  We can actually list an
easy example where unique factorization fails.
\par Consider the class $C$ of positive even integers.  Note that $C$ is closed under multiplication,
which means that the product of any two elements in $C$ is again in $C$.
Suppose now that the only number we know are the members of $C$.
Then we have $12=2.6$ is composite where as $14$ is prime since it is not the product of two numbers in $C$.
Now notice that $60=2.30=6.10$ and thus the factorization is not unique.
\par We now give examples of the unique factorization of integers.
\index{Factorization}
\begin{example}
$99=3\cdot 3\cdot 11=3^2\cdot 11$, \ \ \ $32=2\cdot 2\cdot 2\cdot 2\cdot 2=2^5$
\end{example}

\subsection{The Fundamental Theorem of Arithmetic}
To prove the fundamental theorem of arithmetic, we need to prove
some lemmas about divisibility.

\begin{lemma}\label{lemma4}
If a,b,c are positive integers such that $(a,b)=1$ and $a \mid bc$,
then $a\mid c$.
\end{lemma}

\begin{proof}
Since $(a,b)=1$, then there exists integers $x,y$ such that
$ax+by=1$. As a result, $cax+cby=c$.  Notice that since $a \mid bc$,
then by Theorem 4,  $a$ divides $cax+cby$ and hence $a$ divides $c$.
\end{proof}

We can generalize the above lemma as such: If $(a_,n_i)=1$ for every
$i=1,2,\cdots,n$ and $a\mid n_1n_2\cdots n_{k+1}$, then $a\mid
n_{k+1}$. We next prove a case of this generalization and use this
to prove the fundamental theorem of arithmetic.

\begin{lemma}\label{lemma5}
If $p$ divides $n_1n_2n_3...n_k$, where p is a prime and $n_i >0$
for all $1\leq i\leq k$, then there is an integer $j$ with $1\leq
j\leq k$ such that $p \mid n_j$.
\end{lemma}

\begin{proof}
We present the proof of this result by induction.  For $k=1$, the
result is trivial.  Assume now that the result is true for $k$.
Consider $n_1n_2...n_{k+1}$ that is divisible by $p$.  Notice that
either
\begin{equation*}
(p,n_1n_2...n_k)=1\ \  \mbox{or}  \ \ (p,n_1n_2...n_{k})=p.
\end{equation*}
Now if $(p,n_1n_2...n_k)=1$ then by Lemma 4, $p \mid n_{k+1}$. Now
if $p\mid n_1n_2...n_k$, then by the induction hypothesis, there
exists an integer $i$ such that $p\mid n_i$.
\end{proof}

We now state the fundamental theorem of arithmetic and present the
proof using Lemma 5. \index{Fundamental Theorem of Arithmetic}
\begin{theorem}\label{fta}
\textbf{The Fundamental Theorem of Arithmetic}  Every positive
integer different from 1 can be written uniquely as a product of
primes.
\end{theorem}

\begin{proof}
If $n$ is a prime integer, then $n$ itself stands as a product of
primes with a single factor.  If $n$ is composite, we use proof by
contradiction.  Suppose now that there is some positive integer that
cannot be written as the product of primes.  Let $n$ be the smallest
such integer.  Let $n=ab$, with $1<a<n$ and $1<b<n$.  As a result
$a$ and $b$ are products of primes since both integers are less than
$n$.  As a result, $n=ab$ is a product of primes, contradicting that it is not. This shows that
every integer can be written as product of primes. We now prove that
the representation of a positive integer as a product of primes is
unique.  Suppose now that there is an integer $n$ with two different
factorizations say
\begin{equation*}
n=p_1p_2...p_s=q_1q_2...q_r
\end{equation*}
where $p_1,p_2,...p_s,q_1,q_2,...q_r$ are primes,
\begin{equation*}
 p_1\leq p_2 \leq
p_3\leq ...\leq p_s \mbox{and} \ \  q_1 \leq q_2 \leq q_3 \leq ...
\leq q_r.
\end{equation*}
Cancel out all common primes from the factorizations above to get
\begin{equation*}
p_{j_1}p_{j_2}...p_{j_u}=q_{i_1}q_{i_2}...q_{i_v}
\end{equation*}
Thus all the primes on the left side are different from the primes
on the right side. Since any $p_{j_l}$ $(l=1,\cdots,n)$ divides $p_{j_1}p_{j_2}...p_{j_u}$,
then $p_{j_l}$ must divide $q_{i_1}q_{i_2}...q_{i_v}$, and hence by Lemma 5, $p_{j_1}$ must divide $q_{j_k}$ for
some $1\leq k \leq v$ which is impossible.  Hence the representation
is unique.
\end{proof}

\begin{remark}\label{remark1}
The unique representation of a positive integer $n$ as a product of
primes can be written in several ways.  We will present the most
common representations. For example, $n=p_1p_2p_3...p_k$ where $p_i$
for $1\leq i\leq k$ are not necessarily distinct. Another example
would be
\begin{equation}
n=p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_j^{a_j}
\end{equation}
where all the
$p_i$ are distinct for $1\leq i\leq j$. One can also write a formal product
\begin{equation}
n=\prod_{all\hspace{0.1cm} primes\hspace{0.1cm} p_i}p_i^{\alpha_i},
\end{equation}
where all but finitely many of the $\alpha_i's$ are 0.
\end{remark}


\begin{example}
The prime factorization of 120 is given by $120=2\cdot 2\cdot 2\cdot
3\cdot 5=2^3\cdot 3\cdot 5$. Notice that 120 is written in the two
ways described in \ref{remark1}.
\end{example}

We know describe in general how prime factorization can be used to
determine the greatest common divisor of two integers. Let
\begin{equation*}
a=p_1^{a_1}p_2^{a_2}...p_n^{a_n} \hspace{0.3cm}\mbox{and} \ \
b=p_1^{b_1}p_2^{b_2}...p_n^{b_n},
\end{equation*}
where we exclude in these expansions any prime $p$ with power 0 in both $a$ and $b$
(and thus some of the powers above may be 0 in one expansion but not the other). Of course,
if one prime $p_i$ appears in $a$ but not in $b$, then
$a_i\neq 0$ while $b_i=0$, and vise versa. Then the greatest common divisor is given by
\begin{equation*}
(a,b)=p_1^{\min(a_1,b_2)}p_2^{min(a_2,b_2)}...p_n^{\min(a_n,b_n)}
\end{equation*}
where $\min(n,m)$ is the minimum of $m$ and $n$.
\par The following lemma is a consequence of the Fundamental
Theorem of Arithmetic.

\begin{lemma}
Let $a$ and $b$ be relatively prime positive integers.  Then if $d$
divides $ab$, there exists $d_1$ and $d_2$ such that $d=d_1d_2$
where $d_1$ is a divisor of $a$ and $d_2$ is a divisor of $b$.
Conversely, if $d_1$ and $d_2$ are positive divisors of $a$ and $b$,
respectively, then $d=d_1d_2$ is a positive divisor of $ab$.
\end{lemma}

\begin{proof}
Let $d_1=(a,d)$ and $d_2=(b,d)$.  Since $(a,b)=1$ and writing $a$
and $b$ in terms of their prime decomposition, it is clear that
$d=d_1d_2$ and $(d_1,d_2)=1$. Note that every prime power in the
factorization of $d$ must appear in either $d_1$ or $d_2$. Also the
prime powers in the factorization of $d$ that are prime powers
dividing $a$ must appear in $d_1$ and that prime powers in the
factorization of $d$ that are prime powers dividing $b$ must appear
in $d_2$.
\par Now conversely, let $d_1$ and $d_2$ be positive divisors of
$a$ and $b$, respectively.  Then
\begin{equation*}
d=d_1d_2
\end{equation*}
is a divisor of $ab$.
\end{proof}


\subsection{More on the Infinitude of Primes}

There are also other theorems that discuss the infinitude of primes
in a given arithmetic progression.  The most famous theorem about
primes in arithmetic progression is Dirichlet's theorem
\begin{theorem}
\textbf{Dirichlet's Theorem} Given an arithmetic progression of
terms $an+b$ , for $n=1, 2, ...$ ,the series contains an infinite
number of primes if  $a$ and $b$ are relatively prime,
\end{theorem}\index{Dirichlet's Theorem}
This result had been conjectured by Gauss but was first proved by
Dirichlet. Dirichlet proved this theorem using complex analysis, but
the proof is so challenging.  As a result, we will present a special
case of this theorem and prove that there are infinitely many primes
in a given arithmetic progression.  Before stating the theorem about
the special case of Dirichlet's theorem, we prove a lemma that will
be used in the proof of the mentioned theorem.

\begin{lemma}
If $a$ and $b$ are integers both of the form $4n+1$, then their
product $ab$ is of the form $4n+1$
\end{lemma}

\begin{proof}
Let $a=4n_1+1$ and $b=4n_2+1$, then
\begin{equation*}
ab=16n_1n_2+4n_1+4n_2+1=4(4n_1n_2+n_1+n_2)+1=4n_3+1,
\end{equation*}
where $n_3=4n_1n_2+n_1+n_2$.
\end{proof}

\begin{theorem}
There are infinitely many primes of the form $4n+3$, where $n$ is a
positive integer.
\end{theorem}

\begin{proof}
Suppose that there are finitely many primes of the form $4n+3$, say
$p_0=3,p_1,p_2,...,p_n$.  Let
\begin{equation*}
N=4p_1p_2...p_n+3.
\end{equation*}
Notice that any odd prime is of the form $4n+1$ or $4n+3$.  Then
there is at least one prime in the prime factorization of $N$ of the
form $4n+3$, as otherwise, by Lemma 7, $N$ will be in the form $4n+1$.
We wish to prove that this prime in the factorization of $N$ is none
of $p_0=3,p_1,p_2,...,p_n$. Notice that if
\begin{equation*}
3\mid N,
\end{equation*}
then $3 \mid (N-3)$ and hence
\begin{equation*}
3 \mid 4p_1p_2...p_n
\end{equation*}
which is impossible since $p_i\neq 3$ for every $i$. Hence 3 doesn't divide $N$. Also, the other
primes $p_1,p_2,...,p_n$ don't divide $N$ because if $p_i \mid N$,
then
\begin{equation*}
p_i\mid (N-4p_1p_2...p_n)=3.
\end{equation*}
Hence none of the primes $p_0,p_1,p_2,...,p_n$ divides N. Thus
there are infinitely many primes of the form $4n+3$.
\end{proof}


 \textbf{Exercises}
\begin{enumerate}
\item{Find the prime factorization of 32, of 800 and of
289.}\item{Find the prime factorization of 221122 and of
9!.}\item{Show that all the powers of in the prime factorization of
an integer $a$ are even if and only if a is a perfect
square.}\item{Show that there are infinitely many primes of the form
$6n+5$.}
\end{enumerate}



\index{Least Common Multiple}
\section{Least Common Multiple}
We can use prime factorization to find the smallest common multiple
of two positive integers.

\begin{definition}
The least common multiple (l.c.m.) of two positive integers is the
smallest positive integer that is a multiple of both.
\end{definition}

We denote the least common multiple of two positive integers $a$ an
$b$ by $\langle a,b\rangle$.

\begin{example}
$\langle2,8\rangle=8$, $\langle5,8\rangle=40$
\end{example}

We can figure out $\langle a,b\rangle$ once we have the prime
factorization of $a$ and $b$.  To do that, let
\begin{equation*}
a=p_1^{a_1}p_2^{a_2}...p_m^{a_n}  \hspace{0.2cm}\mbox{and}\ \
b=p_1^{b_1}p_2^{b_2}...p_m^{b_n},
\end{equation*}
where (as above) we exclude any prime with 0 power in both $a$ and $b$. Then $\langle
a,b\rangle=p_1^{\max(a_1,b_1)}p_2^{\max(a_2,b_2)}...p_m^{\max(a_n,b_n)}$,
where $\max(a,b)$ is the maximum of the two integers $a$ and $b$. We
now prove a theorem that relates the least common multiple of two
positive integers to their greatest common divisor.  In some books,
this theorem is adopted as the definition of the least common
multiple.  To prove the theorem we present a lemma

\begin{lemma}
If a and b are two real numbers, then
\begin{equation*}
\min(a,b)+\max(a,b)=a+b
\end{equation*}
\end{lemma}

\begin{proof}
Assume without loss of generality that $a\geq b$.  Then
\begin{equation*}
\max(a,b)=a \hspace{0.2cm}\mbox{and} \ \  \min(a,b)=b,
\end{equation*}
and the result follows.
\end{proof}

\begin{theorem}
Let $a$ and $b$ be two positive integers.  Then
\begin{enumerate}
 \item {$\langle a,b\rangle\geq 0$};
 \item {$\langle a,b \rangle=ab/(a,b)$};
\item{If $a\mid m$ and $b \mid m$, then $\langle a,b \rangle \mid
m$}
\end{enumerate}
\end{theorem}

\begin{proof}
The proof of part 1 follows from the definition.  \\
As for part 2, let
\begin{equation*}
a=p_1^{a_1}p_2^{a_2}...p_m^{a_n} \mbox{and} \ \
b=p_1^{b_1}p_2^{b_2}...p_m^{b_n}.
\end{equation*}
Notice that since
\begin{equation*}
(a,b)=p_1^{\min(a_1,b_2)}p_2^{\min(a_2,b_2)}...p_n^{\min(a_n,b_n)}
\end{equation*}
and
\begin{equation*}
\langle
a,b\rangle=p_1^{\max(a_1,b_1)}p_2^{\max(a_2,b_2)}...p_m^{\max(a_n,b_n)},
\end{equation*}
then
\begin{eqnarray*}
\langle a,b
\rangle(a,b)&=&p_1^{\max(a_1,b_1)}p_2^{\max(a_2,b_2)}...p_m^{\max(a_n,b_n)}
p_1^{\min(a_1,b_2)}p_2^{min(a_2,b_2)}...p_n^{\min(a_n,b_n)}\\ &=&
p_1^{\max(a_1,b_1)+\min(a_1,b_1)}p_2^{\max(a_2,b_2)+\min(a_2,b_2)}...p_m^{\max(a_n,b_n)+\min(a_n,b_n)}\\&=&
p_1^{a_1+b_1}p_2^{a_2+b_2}...p_n^{(a_n+b_n)}\\&=&p_1^{a_1}p_2^{a_2}...p_m^{a_n}p_1^{b_1}p_2^{b_2}...p_m^{b_n}=ab
\end{eqnarray*}
Note also that we used Lemma 8 in the above equations.  For part
3, it would be a nice exercise to show that $ab/(a,b) \mid m$
(Exercise 6). Thus $\langle a,b \rangle \mid m$.
\end{proof}

\textbf{Exercises}
\begin{enumerate}
\item{Find the least common multiple of 14 and 15.}\item{Find the
least common multiple of 240 and 610.}\item{Find the least common
multiple and the greatest common divisor of $2^55^67^211$ and
$2^35^87^213$.}\item{Show that every common multiple of two positive
integers $a$ and $b$ is divisible by the least common multiple of
$a$ and $b$.}\item{Show that if $a$ and $b$ are positive integers
then the greatest common divisor of $a$ and $b$ divides their least
common multiple.  When are the least common multiple and the
greatest common divisor equal to each other.}
\item{Show that $ab/(a,b) \mid m$ where $m=<a,b>$.}
\end{enumerate}




\section{Linear Diophantine Equations}
\index{Diophantine Equations} In this section, we discuss equations
in two variables called diophantine equations.  These kinds of
equations require integer solutions.  The goal of this section is to
present the set of points that determine the solution to this kind
of equations. Geometrically speaking, the diophantine equation
represent the equation of a straight line.  We need to find the
points whose coordinates are integers and through which the straight
line passes. \index{Linear Equation}
\begin{definition}
A linear equation of the form $ax+by=c$ where $a,b$ and $c$ are
integers is known as a linear diophantine equation.
\end{definition}

Note that a solution to the linear diophantine equation $(x_0,y_0)$
requires $x_0$ and $y_0$ to be integers.  The following theorem
describes the case in which the diophantine equation has a solution
and what are the solutions of such equations.

\begin{theorem}
The equation $ax+by=c$ has integer solutions if and only if $d\mid
c$ where $d=(a,b)$.  If the equation has one solution $x=x_0$,
$y=y_0$, then there are infinitely many solutions and the solutions
are given by
\begin{equation*}
x=x_0+(b/d)t \ \ \ \ \ y=y_0-(a/d)t
\end{equation*}
where $t$ is an arbitrary integer.
\end{theorem}

\begin{proof}
Suppose that the equation $ax+by=c$ has integer solution $x$ and
$y$.  Thus since $d\mid a$ and $d\mid b$, then
\begin{equation*}
d\mid (ax+by)=c.
\end{equation*}
Now we have to prove that if $d\mid c$, then the equation has
integral solution.  Assume that $d\mid c$. By theorem 9, there exist
integers $m$ and $n$ such that
\begin{equation*}
d=am+bn.
\end{equation*}
And also there exists integer $k$ such that
\begin{equation*}
c=dk
\end{equation*}
Now since $c=ax+by$, we have
\begin{equation*}
c=dk=(ma+nb)k=a(km)+b(nk).
\end{equation*}
Hence a solution for the equation $ax+by=c$ is
\begin{equation*}
x_0=km \ \ \mbox{and} \ \  y_0=kn.
\end{equation*}
What is left to prove is that we have infinitely many solutions.
Let
\begin{equation*}
x=x_0+(b/d)t \ \ \mbox{and} \ \  y=y_0-(a/d)t.
\end{equation*}
We have to prove now that $x$ and $y$ are solutions for all integers
$t$. Notice that
\begin{equation*}
ax+by=a(x_0+(b/d)t)+b(y_0-(a/d)t)=ax_0+by_0=c.
\end{equation*}
We now show that every solution for the equation $ax+by=c$
is of the form
\begin{equation*}
x=x_0+(b/d)t \mbox{and} \ \  y=y_0-(a/d)t.
\end{equation*}
Notice that since $ax_0+by_0=c$, we have
\begin{equation*}
a(x-x_0)+b(y-y_0)=0.
\end{equation*}
Hence
\begin{equation*}
a(x-x_0)=b(y-y_0).
\end{equation*}
Dividing both sides by $d$, we get
\begin{equation*}
a/d(x-x_0)=b/d(y-y_0).
\end{equation*}
Notice that $(a/d,b/d)=1$ and thus we get by Lemma 4 that $a/d\mid
y-y_0$. As a result, there exists an integer $t$ such that
$y=y_0-(a/d)t$. Now substituting $y-y_0$ in the equation
\begin{equation*}
a(x-x_0)=b(y-y_0).
\end{equation*}
We get
\begin{equation*}
x=x_0+(b/d)t.
\end{equation*}
\end{proof}

\begin{example}
The equation $3x+6y=7$ has no integer solution because $(3,6)=3$
does not divide $7$.
\end{example}

\begin{example}
There are infinitely many integer solutions for the equation
$4x+6y=8$ because $(4,6)=2 \mid 8$.  We use the Euclidean algorithm
to determine $m$ and $n$ where $4m+6n=2$.  It turns out that
$4(-1)+6(1)=2$. And also $8=2.4$. Thus $x_0=4.(-1)=-4$ and
$y_0=4.1=4$ is a particular solution. The solutions are given by
\begin{equation*}
x=-4+3t \ \ \ \ \  y=4-2t
\end{equation*}
for all integers $t$.
\end{example}

\textbf{Exercises}
\begin{enumerate}
\item{Either find all solutions or prove that there are no
solutions for the diophantine equation $21x+7y=147.$}\item{Either
find all solutions or prove that there are no solutions for the
diophantine equation $2x+13y=31.$}\item{Either find all solutions or
prove that there are no solutions for the diophantine equation
$2x+14y=17.$}\item{A grocer orders apples and bananas at a total
cost of \$8.4.  If the apples cost 25 cents each and the bananas 5
cents each, how many of each type of fruit did he order.}
\end{enumerate}



\section{The function $[x]$ , the symbols "O", "o" and  "$\sim$"}
We start this section by introducing an important number theoretic
function.  We proceed in defining some convenient symbols that will
be used in connection with the growth and behavior
of some functions that will be defined in later chapters.  \\


\subsection{The Function $[x]$}. \index{The Function [x]}
\begin{definition}
The function $[x]$ represents the largest integer not exceeding $x$.
In other words, for real $x$, $[x]$ is the unique integer such that
\begin{equation*}
x-1<[x]\leq x<[x]+1.
\end{equation*}
\end{definition}

We also define $((x))$ to be the fractional part of $x$.  In other
words $((x))=x-[x]$. \\
We now list some properties of $[x]$ that will be used in later or
in more advanced courses in number theory.
\begin{enumerate}
\item{$[x+n]=[x]+n$, if $n$ is an integer.} \item{$[x]+[y]\leq
[x+y]$.} \item{$[x]+[-x]$ is 0 if $x$ is an integer and -1
otherwise.} \item{The number of integers $m$ for which $x<m\leq y$
is $[y]-[x]$.} \item{The number of multiples of $m$ which do not
exceed $x$ is $[x/m]$.}
\end{enumerate}

Using the definition of $[x]$, it will be easy to see that the
above properties are direct consequences of the definition.\\
We now define some symbols that will be used to estimate the growth
of number theoretic functions.  These symbols will be not be really
appreciated in the context of this book but these are often used in
many analytic proofs.

\subsection{The "O" and "o" Symbols}

\par Let $f(x)$ be a positive function and let $g(x)$ be any function.  Then $O(f(x))$
(pronounced "big-oh" of $f(x)$)denotes the collection of functions $g(x)$ that exhibit a growth that
is limited to that of $f(x)$ in some respect. The traditional notation
for stating that $g(x)$ belongs to this collection is:
\begin{equation*}
g(x)=O(f(x)).
\end{equation*}
This means that for sufficiently large $x$,
\begin{equation}
\frac{\mid g(x)\mid }{|f(x)|}<M,
\end{equation}
where $M$ is some positive number.


\begin{example}
$\sin (x)=O(x)$, and also $\sin(x)=O(1)$.
\end{example}
\index{small-oh} Now, the relation $g(x)=o(f(x))$, pronounced
"small-oh" of $f(x)$, is used to indicate that $f(x)$ grows much
faster than $g(x)$.  It formally says that
\begin{equation}
\lim_{x\rightarrow \infty}\frac{g(x)}{f(x)}=0.
\end{equation}
More generally, $g(x)=o(f(x))$ at a point $b$ if
\begin{equation}
\lim_{x\rightarrow b}\frac{g(x)}{f(x)}=0.
\end{equation}

\begin{example}
$\sin(x)=o(x)$ at $\infty$, and $x^k=o(e^x)$ also at $\infty$ for every constant $k$.
\end{example}

The notation that $f(x)$ is asymptotically \index{asymptotic}equal
to $g(x)$ is denoted by $\sim$.  Formally speaking, we say that
$f(x) \sim g(x)$ if

\begin{equation}
\lim_{x\rightarrow \infty}\frac{f(x)}{g(x)}=1.
\end{equation}

\begin{example}
$[x] \sim x$.
\end{example}

The purpose of introducing these symbols is to make complicated
mathematical expressions simpler.  Some expressions can be
represented as the principal part that you need plus a remainder
term.  The remainder term can be expressed using the above
notations.  So when you need to combine several expressions, the
remainder parts involving these symbols can be easily combined. We
will state now some properties of the above symbols without proof.
These properties are easy to prove using the definitions of the
symbols.
\begin{enumerate}
\item{$O(O(f(x)))=O(f(x))$,}\item{$o(o(f(x)))=o(f(x))$.}
\item{$O(f(x))\pm O(f(x))=O(f(x))$,} \item{$o(f(x)\pm
o(f(x))=o(f(x))$,} \item{$O(f(x))\pm O(g(x))=O(\max(f(x), g(x)))$,}
\end{enumerate}
There are some other properties that we did not mention here,
properties that are rarely used in number theoretic proofs.\\
\textbf{Exercises}
\begin{enumerate}
\item{Prove the five properties of the $[x]$}
\item{Prove the five properties of the $O$ and $o$ notations in Example 24.}
\end{enumerate}


\section{Theorems and Conjectures involving prime numbers}
We have proved that there are infinitely many primes.  We have also
proved that there are arbitrary large gaps between primes.  The
question that arises naturally here is the following: Can we
estimate how many primes are there less than a given number?  The
theorem that answers this question is the prime number theorem.  We
denote by $\pi(x)$ the number of primes less than a given positive
number $x$. Many mathematicians worked on this theorem and
conjectured many estimates before Chebyshev finally stated that the
estimate is $x/log x$.  The prime number theorem was finally proved
in 1896 when Hadamard and Poussin produced independent proofs.
Before stating the prime number theorem, we state and prove a lemma
involving primes that will be used in the coming chapters.

\begin{lemma}
Let $p$ be a prime and let $m\in \mathbb{Z^+}$. Then the highest
power of $p$ dividing $m!$ is
\begin{equation*}
\sum_{i=1}^\infty\left[\frac{m}{p^i}\right]
\end{equation*}
\end{lemma}

\begin{proof}
Among all the integers from 1 till $m$, there are exactly
$\left[\frac{m}{p}\right]$ integers that are divisible by $p$. These
are $p,2p,...,\left[\frac{m}{p}\right]p$.  Similarly we see that
there are $\left[\frac{m}{p^i}\right]$ integers that are divisible
by $p^i$. As a result, the highest power of $p$ dividing $m!$ is
\begin{equation*}
\sum_{i\geq
1}i\left\{\left[\frac{m}{p^i}\right]-\left[\frac{m}{p^{i+1}}\right]\right\}=\sum_{i\geq
1} \left[\frac{m}{p^i}\right]
\end{equation*}
\end{proof}
\index{Prime Number Theorem}
\begin{theorem}
\textbf{The Prime Number Theorem} Let $x>0$ then
\begin{equation*}
\pi(x)\sim x/log x
\end{equation*}
\end{theorem}

So this theorem says that you do not need to find all the primes
less than $x$ to find out their number, it will be enough to
evaluate $x/log x$ for large $x$ to find an estimate for the number
of primes. Notice that I mentioned that $x$ has to be large enough
to be able to use this estimate.

\par Several other theorems were proved concerning prime numbers.
many great mathematicians approached problems that are related to
primes.  There are still many open problems of which we will
mention some.\\

\begin{conjecture} \index{Twin Prime Conjecture}
\textbf{Twin Prime Conjecture}  There are infinitely many pairs
primes $p$ and $p+2$.
\end{conjecture}

\begin{conjecture} \index{Goldbach's Conjecture}
\textbf{Goldbach's Conjecture} Every even positive integer greater
than 2 can be written as the sum of two primes.
\end{conjecture}

\begin{conjecture}
\textbf{The $n^2+1$ Conjecture} There are infinitely many primes of
the form $n^2+1$, where $n$ is a positive integer.
\end{conjecture}

\begin{conjecture} \index{Polignac Conjecture}
\textbf{Polignac Conjecture} For every even number $2n$ are there
infinitely many pairs of consecutive primes which differ by $2n$.
\end{conjecture}

\begin{conjecture}\index{Opperman Conjecture}
\textbf{Opperman Conjecture} Is there always a prime between $n^2$
and $(n+1)^2$?
\end{conjecture}







\chapter{Congruences}

A congruence is nothing more than a statement about divisibility.
The theory of congruences was introduced by Carl Friedreich Gauss.
Gauss contributed to the basic ideas of congruences and proved
several theorems related to this theory. We start by introducing
congruences and their properties.  We proceed to prove theorems
about the residue system in connection with the Euler
$\phi$-function.  We then present solutions to linear congruences
which will serve as an introduction to the Chinese remainder
theorem.    We present finally important congruence theorems derived
by Wilson, Fermat and Euler.

\section{Introduction to congruences}
As we mentioned in the introduction, the theory of congruences was
developed by Gauss at the beginning of the nineteenth century.
\index{Congruence}
\begin{definition}
Let m be a positive integer. We say that $a$ is congruent to $b$
modulo m if $m \mid (a-b)$ where $a$ and $b$ are integers, i.e. if $a=b+km$ where $k\in \mathbb{Z}$.
\end{definition}
\index{Modulo} If $a$ is congruent to $b$ modulo $m$, we write
$a\equiv b(mod\ m)$.

\begin{example}
$19\equiv 5 (mod \ 7)$.  Similarly $2k+1 \equiv 1 (mod\ 2)$ which
means every odd number is congruent to 1 modulo 2.
\end{example}

There are many common properties between equations and congruences.
Some properties are listed in the following theorem.

\begin{theorem}
Let $a, b, c$ and $d$ denote integers.  Let $m$ be a
positive integers.  Then:

\begin{enumerate}
\item{If $a \equiv b(mod \ m)$, then $b\equiv a (mod \ m)$.}
\item{If $a\equiv b(mod \ m)$ and $b\equiv c(mod \ m)$, then
$a\equiv c (mod \ m)$.}
\item{If $a\equiv b(mod\ m)$, then $a+c
\equiv b+c (mod \ m)$.}
\item{If $a\equiv b(mod\ m)$, then $a-c
\equiv b-c (mod \ m)$.}
\item{If $a\equiv b(mod\ m)$, then $ac
\equiv bc (mod \ m)$.}
\item{If $a\equiv b(mod\ m)$, then $ac \equiv
bc (mod \ mc)$, for $c>0$.}
\item{If $a\equiv b(mod\ m)$ and $c
\equiv d (mod \ m)$ then $a+c \equiv (b+d) (mod \ m)$.}
\item{If
$a\equiv b(mod\ m)$ and $c \equiv d (mod \ m)$ then $a-c \equiv (b-d)
(mod \ m)$.}
\item{If $a\equiv b(mod\ m)$ and $c \equiv d (mod \ m)$
then $ac \equiv bd (mod \ m)$.}
\end{enumerate}
\end{theorem}

\begin{proof}
\begin{enumerate}
\item{If $a \equiv b(mod \ m)$, then $m\mid (a-b)$. Thus there
exists integer $k$ such that $a-b=mk$, this implies $b-a=m(-k)$ and
thus $m\mid (b-a)$.  Consequently $b\equiv a (mod \ m)$.}

\item{Since $a\equiv b(mod \ m)$, then $m\mid (a-b)$. Also,
$b\equiv c(mod \ m)$, then $m\mid (b-c)$.  As a result, there exit
two integers $k$ and $l$ such that $a=b+mk$ and $b=c+ml$, which imply that $a=c+m(k+l)$ giving that $a=c (mod \ m)$.}

\item{Since $a\equiv b (mod \ m)$, then $m \mid (a-b)$. So if we
add and subtract $c$ we get
\begin{equation*}
m\mid ((a+c)-(b+c))
\end{equation*}
and as a result
\begin{equation*}
a+c\equiv b+c (mod \ m). \end{equation*}}
\item{Since $a\equiv b (mod \ m)$, then $m \mid (a-b)$ so we can
subtract and add $c$ and we get
\begin{equation*}
m\mid ((a-c)-(b-c))
\end{equation*}
and as a result
\begin{equation*}
a-c\equiv b-c (mod \ m). \end{equation*}}
\item{If $a \equiv b(mod \ m)$, then $m\mid (a-b)$. Thus there
exists integer $k$ such that $a-b=mk$ and as a result $ac-bc=m(kc)$.
Thus
\begin{equation*}
m\mid (ac-bc)
\end{equation*}
and hence
\begin{equation*}
ac\equiv bc (mod \ m). \end{equation*}}
\item{If $a \equiv b(mod \
m)$, then $m\mid (a-b)$. Thus there exists integer $k$ such that
$a-b=mk$ and as a result
\begin{equation*}
ac-bc=mc(k).
\end{equation*}
Thus
\begin{equation*}
mc\mid (ac-bc)
\end{equation*}
and hence
\begin{equation*}
ac\equiv bc (mod \ mc). \end{equation*}}
\item{Since $a\equiv b(mod \ m)$, then $m\mid (a-b)$. Also, $c\equiv
d(mod \ m)$, then $m\mid (c-d)$. As a result, there exits two
integers $k$ and $l$ such that $a-b=mk$ and $c-d=ml$. Note that
\begin{equation*}
(a-b)+(c-d)=(a+c)-(b+d)=m(k+l).
\end{equation*}
As a result,
\begin{equation*}
m\mid ((a+c)-(b+d)),
\end{equation*}
hence
\begin{equation*}
a+c\equiv b+d(mod \ m).\end{equation*}}

\item{If $a=b+mk$ and $c=d+ml$ where $k$ and $l$ are integers, then
\begin{equation*}
(a-b)-(c-d)=(a-c)-(b-d)=m(k-l).
\end{equation*}
As a result,
\begin{equation*}
m\mid ((a-c)-(b-d)),
\end{equation*}
hence
\begin{equation*}
a-c\equiv b-d(mod \ m). \end{equation*}}

\item{There exit two integers $k$ and $l$
such that $a-b=mk$ and $c-d=ml$ and thus $ca-cb=m(ck)$ and
$bc-bd=m(bl)$. Note that
\begin{equation*}
(ca-cb)+(bc-bd)=ac-bd=m(kc-lb).
\end{equation*}
As a result, \begin{equation*}m\mid (ac-bd), \end{equation*}hence
\begin{equation*}
ac\equiv bd(mod \ m). \end{equation*}}
\end{enumerate}
\end{proof}


\begin{examples}
\begin{enumerate}
\item{Because $ 14\equiv 8(mod\  6)$ then $8 \equiv 14 (mod\ 6)$.}
\item{Because $22\equiv 10(mod \ 6)$ and $10 \equiv 4(mod \ 6)$.
Notice that $22\equiv 4(mod \ 6)$.}\item{Because $50\equiv 20 (mod\
15)$, then $50+5=55\equiv 20+5=25(mod\ 15)$.}\item{Because $50\equiv
20 (mod\ 15)$, then $50-5=45\equiv 20-5=15(mod\ 15)$.}\item{Because
$19\equiv 16(mod3)$, then $2(19)=38\equiv 2(16)=32(mod \
3).$}\item{Because $19\equiv 16(mod3)$, then $2(19)=38\equiv
2(16)=32(mod \ 2(3)=6).$}\item{Because $19\equiv 3 (mod \ 8)$ and
$17\equiv 9(mod \ 8)$, then $19+17=36\equiv 3+9=12(mod \
8)$}.\item{Because $19\equiv 3 (mod \ 8)$ and $17\equiv 9(mod \ 8)$,
then $19-17=2\equiv 3-9=-6(mod \ 8)$}.\item{Because $19\equiv 3 (mod
\ 8)$ and $17\equiv 9(mod \ 8)$, then $19(17)=323\equiv 3(9)=27(mod
\ 8)$}.
\end{enumerate}

\end{examples}

We now present a theorem that will show one difference between
equations and congruences.  In equations, if we divide both sides of
the equation by a non-zero number, equality holds.  While in
congruences, it is not necessarily true.  In other words, dividing
both sides of the congruence by the same integer doesn't preserve
the congruence.

\begin{theorem}
\begin{enumerate}
\item {If $a,b, c$ and $m$ are integers such that $m>0$, $d=(m,c)$ and
$ac\equiv bc(mod \ m)$, then $a\equiv b (mod \ m/d)$.}
\item {If $(m,c)=1$ then $a=b(mod \ m)$ if $ac\equiv bc(mod \ m)$.}
\end{enumerate}
\end{theorem}

\begin{proof}
Part 2 follows immediately from Part 1. For Part 1, if $ac\equiv
bc(mod \ m)$, then
\begin{equation*}
m\mid (ac-bc)=c(a-b).
\end{equation*}
Hence there exists $k$ such that $c(a-b)=mk$. Dividing both sides by
$d$, we get $(c/d)(a-b)=k(m/d)$. Since $(m/d,c/d)=1$,  it follows
that $m/d \mid (a-b)$.  Hence $a\equiv b (mod \ m/d)$.
\end{proof}

\begin{example}
$38 \equiv 10 (mod\ 7)$.  Since $(2,7)=1$ then $19\equiv 5 (mod \
7).$
\end{example}

The following theorem combines several congruences of two numbers
with different moduli.

\begin{theorem}
If
\begin{equation*}
a\equiv b(mod \ m_1), a\equiv b(mod \ m_2),...,a\equiv b(mod \ m_t)
\end{equation*}
where $a,b,m_1,m_2,...,m_t$ are integers and $m_1,m_2,...,m_t$ are
positive, then
\begin{equation*}
a\equiv b(mod \ \langle m_1,m_2,...m_t\rangle)
\end{equation*}
\end{theorem}

\begin{proof}
Since $a\equiv b (mod \ m_i)$ for all $1\leq i\leq t$.  Thus $m_i
\mid (a-b)$.  As a result,
\begin{equation*}
\langle m_1,m_2,...,m_t\rangle \mid (a-b)
\end{equation*}
(prove this as an exercise).  Thus
\begin{equation*}
a\equiv b(mod \ \langle m_1,m_2,...m_t\rangle). \end{equation*}
\end{proof}

\textbf{Exercises}
\begin{enumerate}
\item{Determine whether 3 and 99 are congruent modulo 7 or not.}
\item{Show that if $x$ is an odd integer, then $x^2\equiv 1(mod \
8)$} \item{Show that if $a,b, m$ and $n$ are integers such that $m$
and $n$ are positive, $n \mid m$ and $a\equiv b (mod \ m)$, then
$a\equiv b (mod \ n).$}\item{Show that if $a_i\equiv b_i(mod \ m)$
for $i=1,2,...,n$, where $m$ is a positive integer and $a_i,b_i$ are
integers for $j=1,2,...,n$, then $\sum_{i=1}^na_i\equiv
\sum_{i=1}^nb_i(mod \ m)$}\item{For which $n$ does the expression
$1+2+...+(n-1)\equiv 0(mod \ n)$ holds.}

\end{enumerate}



\section{Residue Systems and Euler's $\phi$-Function}

\subsection{Residue Systems} \index{Residue Systems}

Suppose $m$ is a positive integer.  Given two integers $a$ and $b$,
we see that by the division algorithm that $a=bm+r$ where $0\leq
r<m$.  We call $r$ the least nonnegative residue of $a$ modulo $m$.
As a result, we see that any integer is congruent to one of the
integers $0,1,2,...,m-1$ modulo m. \index{Complete Residue System}
\begin{definition}
A complete residue system modulo $m$ is a set of integers such that
every integer is congruent modulo $m$ to exactly one integer of the
set.
\end{definition}
The easiest complete residue system modulo $m$ is the set of
integers $0,1,2,...,m-1$.  Every integer is congruent to one of
these integers modulo m.

\begin{example}
The set of integers $\{0,1,2,3,4\}$ form a complete residue system
modulo $5$.  Another complete residue system modulo $5$ could be
$6,7,8,9,10$.
\end{example}
\index{Reduced Residue System}
\begin{definition}
A reduced residue system modulo $m$ is a set of integers $r_i$ such
that $(r_i,m)=1$ for all $i$ and $r_i \neq r_j (mod \ m)$ if $i\neq
j$.
\end{definition}

Notice that, a reduced residue system modulo $m$ can be obtained by
deleting all the elements of the complete residue system set that
are not relatively prime to $m$.

\begin{example}
The set of integers $\{1,5\}$ is a reduced residue system modulo
$6$.
\end{example}

The following lemma will help determine a complete residue system
modulo any positive integer $m$. \index{Incongruent Integers}
\begin{lemma}
A set of $m$ incongruent integers modulo $m$ forms a complete
residue system modulo $m$.
\end{lemma}

\begin{proof}
We will prove this lemma by contradiction.  Suppose that the set of
$m$ integers does not form a complete residue system modulo $m$.
Then we can find at least one integer $a$ that is not congruent to
any element in this set. Hence non of the elements of this set is
actually congruent to the remainder when $a$ is divided by $m$. Thus
dividing by $m$ yields to at most $m-1$ remainders. Therefore by the
pigeonhole principle, at least two integers in the set that have the
same remainder modulo $m$. This is a contradiction since the set of
integers is formed of $m$ integers that are incongruent modulo $m$.
\end{proof}


\begin{theorem}
If $a_1, a_2,...,a_m$ is a complete residue system modulo $m$, and
if $k$ is a positive integer with $(k,m)=1$, then
\begin{equation*}
ka_1+b, ka_2+b,...,ka_m+b
\end{equation*}
is another complete residue system modulo $m$ for any integer $b$.
\end{theorem}

\begin{proof}
Let us prove first that no two elements of the set $\{ka_1+b,
ka_2+b,...,ka_m+b\}$ are congruent modulo $m$.  Suppose there exists
$i$ and $j$ such that
\begin{equation*}
ka_i+b\equiv ka_j+b(mod\ m).
\end{equation*}
Thus we get that
\begin{equation*}
ka_i\equiv ka_j(mod \ m).
\end{equation*}
Now since $(k,m)=1$, we get
\begin{equation*}
a_i\equiv a_j(mod\ m)
\end{equation*}
But for $i\neq j$, $a_i$ is inequivalent to $a_j$ modulo $m$. Thus
$i=j$. Now notice that there are $m$ inequivalent integers modulo m
and thus by Lemma 10, the set form a complete residue system modulo
$m$.
\end{proof}

\subsection{Euler's $\phi$-Function}

\par We now present a function that counts the number of positive
integers less than a given integer that are relatively prime to that
given integer. This function is called Euler $\phi$-function. We
will discuss the properties of Euler $\phi$-function in details in
chapter 5. It will be sufficient for our purposes in this chapter to
the notation. \index{Euler $\phi$ Function}
\begin{definition}
The Euler $\phi$-function of a positive integer n, denoted by
$\phi(n)$ counts the number of positive integers less than $n$ that
are relatively prime to n.
\end{definition}

\begin{example}
Since 1 and 3 are the only two integers that are relatively prime to
4 and less than 4, then $\phi(4)=2$.  Also, 1,2,...,6 are the
integers that are relatively prime to 7 that are less than 7, thus
$\phi(7)=6$.
\end{example}

Now we can say that the number of elements in a reduced residue
system modulo $n$ is $\phi(n)$.

\begin{theorem}
If $a_1,a_2,...,a_{\phi(n)}$ is a reduced residue system modulo $n$
and $(k,n)=1$, then $ka_1,ka_2,...,ka_{\phi(n)}$ is a reduced
residue system modulo $n$.
\end{theorem}

\begin{proof}
The proof proceeds exactly in the same way as that of Theorem 24.
\end{proof}

\textbf{Exercises}
\begin{enumerate}
\item{Give a reduced residue system  modulo 12.} \item{Give a
complete residue system modulo 13 consisting only of odd
integers.}\item{Find $\phi(8)$ and $\phi(101)$.}
\end{enumerate}


\section{Linear Congruences}
Because congruences are analogous to equations, it is natural to ask
about solutions of linear equations.  In this section, we will be
discussing linear congruences of one variable and their solutions.
We start by defining linear congruences. \index{Linear Congruence}
\begin{definition}
A congruence of the form $ax\equiv b(mod\ m)$ where $x$ is an
unknown integer is called a linear congruence in one variable.
\end{definition}

It is important to know that if $x_0$ is a solution for a linear
congruence, then all integers $x_i$ such that $x_i\equiv x_0 (mod \
m)$ are solutions of the linear congruence. Notice also that
$ax\equiv b (mod\ m)$ is equivalent to a linear Diophantine equation
i.e. there exists $y$ such that $ax-my=b$.  We now prove theorems
about the solutions of linear congruences.

\begin{theorem}
Let $a,b$ and $m$ be integers such that $m>0$ and let $c=(a,m)$. If
$c$ does not divide $b$, then the congruence $ax\equiv b(mod \ m)$
has no solutions. If $c\mid b$, then
\begin{equation*}
ax\equiv b(mod \ m)
\end{equation*}
has exactly $c$ incongruent solutions modulo $m$.
\end{theorem}

\begin{proof}
As we mentioned earlier, $ax\equiv b(mod \ m)$ is equivalent to
$ax-my=b$.  By Theorem 19 on Diophantine equations, we know that if
$c$ does not divide $b$, then the equation, $ax-my=b$ has no
solutions. Notice also that if $c\mid b$, then there are infinitely
many solutions whose variable $x$ is given by
\begin{equation*}
x=x_0+(m/c)t
\end{equation*}
Thus the above values of $x$ are solutions of the congruence
$ax\equiv b(mod \ m)$.  Now we have to determine the number of
incongruent solutions that we have.  Suppose that two solutions are
congruent, i.e.
\begin{equation*}
x_0+(m/c)t_1\equiv x_0+(m/c)t_2(mod \ m).
\end{equation*}
Thus we get
\begin{equation*}
(m/c)t_1\equiv (m/c)t_2(mod \ m).
\end{equation*}
Now notice that $(m,m/c)=m/c$ and thus
\begin{equation*}
t_1\equiv t_2(mod \ c).
\end{equation*}
Thus we get a set of incongruent solutions given by $x=x_0+(m/c)t$,
where $t$ is taken modulo $c$.
\end{proof}

\begin{remark}
Notice that if $c=(a,m)=1$, then there is a unique solution modulo m
for the equation $ax\equiv b(mod \ m)$.
\end{remark}

\begin{example} Let us find all the solutions of the congruence $3x\equiv 12 (mod \
6)$.  Notice that $(3,6)=3$ and $3\mid 12$.  Thus there are three
incongruent solutions modulo $6$.  We use the Euclidean algorithm to
find the solution of the equation $3x-6y=12$ as described in chapter
2. As a result, we get $x_0=6$.  Thus the three incongruent
solutions are given by $x_1=6(mod \ 6)$, $x_1=6+2=2(mod \ 6)$ and
$x_2=6+4=4(mod \ 6)$.
\end{example}

As we mentioned earlier in Remark 2, the congruence $ax\equiv b(mod
\ m)$ has a unique solution if $(a,m)=1$.  This will allow us to
talk about modular inverses.

\begin{definition}
A solution for the congruence $ax\equiv 1 (mod\ m)$ for $(a,m)=1$ is
called the modular inverse of $a$ modulo m. We denote such a solution by $\bar{a}$.
\end{definition} \index{Modular Inverse} \index{Inverse}

\begin{example}
The modular inverse of 7 modulo 48 is 7.  Notice that a solution for
$7x\equiv 1(mod \ 48)$ is $x\equiv 7 (mod \ 48)$.
\end{example}

\textbf{Exercises}
\begin{enumerate}
\item{Find all solutions of $3x\equiv 6(mod \ 9)$.}\item{Find all
solutions of $3x\equiv 2(mod \ 7)$.}\item{Find an inverse modulo 13
of 2 and of 11.}\item{Show that if $\bar{a}$ is the inverse of $a$
modulo $m$ and $\bar{b}$ is the inverse of $b$ modulo $m$, then
$\bar{a}\bar{b}$ is the inverse of $ab$ modulo $m$.}
\end{enumerate}


\section{The Chinese Remainder Theorem}
In this section, we discuss the solution of a system of congruences
having different moduli.  An example of this kind of systems is the
following; find a number that leaves a remainder of 1 when divided
by 2, a remainder of 2 when divided by three and a remainder of 3
when divided by 5.  This kind of question can be translated into the
language of congruences.  As a result, in this chapter, we present a
systematic way of solving this system of congruences. \index{Chinese
Remainder Theorem}
\begin{theorem}
The system of congruences
\begin{eqnarray*}
&& x\equiv b_1(mod \ n_1),\\&&x\equiv b_2(mod \
n_2),\\&&.\\&&.\\&&.\\&& x\equiv b_t(mod \ n_t),
\end{eqnarray*}
has a unique solution modulo $N=n_1n_2...n_t$ if $n_1,n_2,...,n_t$
are pairwise relatively prime positive integers.
\end{theorem}

\begin{proof}
Let $N_k=N/n_k$.  Since $(n_i,n_j)=1$ for all $i\neq j$, then
$(N_k,n_k)=1$.  Hence by Theorem 26 , we can find an inverse $y_k$
of $N_k$ modulo $n_k$ such that $N_ky_k\equiv 1(mod \ n_k)$.
Consider now
\begin{equation*}
x=\sum_{i=1}^tb_iN_iy_i
\end{equation*}
Since
\begin{equation*}
N_j\equiv 0(mod \ n_k) \ \ \mbox{for all} \ \  j\neq k,
\end{equation*}
thus we see that
\begin{equation*}
x\equiv b_kN_ky_k(mod \ n_k).
\end{equation*}
Also notice that $N_ky_k\equiv 1(mod \ n_k)$.  Hence $x$ is a
solution to the system of t congruences.   We have to show now that
any two solutions are congruent modulo $N$.  Suppose now that you
have two solutions $x_0,x_1$ to the system of congruences.  Then
\begin{equation*}
x_0\equiv x_1(mod \ n_k)
\end{equation*}
for all $1\leq k\leq t$.  Thus by Theorem 23, we see that
\begin{equation*}
x_0\equiv x_1(mod \ N).
\end{equation*}
Thus the solution of the system is unique modulo $N$.
\end{proof}

We now present an example that will show how the Chinese remainder
theorem is used to determine the solution of a given system of
congruences.

\begin{example}
Solve the system
\begin{eqnarray*}
&& x\equiv 1(mod \ 2)\\&& x\equiv 2(mod \ 3)\\&& x\equiv 3(mod \ 5).
\end{eqnarray*}
We have $N=2.3.5=30$.  Also
\begin{equation*}
N_1=30/2=15, N_2=30/3=10 \mbox{and} \ \  N_3=30/5=6.
\end{equation*}
So we have to solve now $15y_1\equiv 1(mod \ 2)$. Thus
\begin{equation*}
y_1\equiv 1(mod \ 2).
\end{equation*}
In the same way, we find that
\begin{equation*}
y_2\equiv 1(mod \ 3) \mbox{and} \ \   y_3\equiv 1(mod \ 5).
\end{equation*}
As a result, we get
\begin{equation*}
x\equiv 1.15.1+2.10.1+3.6.1\equiv 53\equiv 23 (mod \ 30).
\end{equation*}
\end{example}

\textbf{Exercises}
\begin{enumerate}
\item{Find an integer that leaves a remainder of 2 when divided by
either 3 or 5, but that is divisible by 4.}\item{Find all integers
that leave a remainder of 4 when divided by 11 and leaves a
remainder of 3 when divided by 17.}\item{Find all integers that
leave a remainder of 1 when divided by 2, a remainder of 2 when
divided by 3 and a remainder of 3 when divided by 5. }
\end{enumerate}


\section{Theorems of Fermat, Euler, and Wilson}
In this section we present three applications of congruences. The
first theorem is Wilson's theorem which states that $(p-1)!+1$ is
divisible by $p$, for $p$ prime.  Next, we present Fermat's theorem,
also known as Fermat's little theorem which states that $a^p$ and
$a$ have the same remainders when divided by $p$ where $p\nmid a$.
Finally we present Euler's theorem which is a generalization of
Fermat's theorem and it states that for any positive integer $m$
that is relatively prime to an integer $a$, $a^{\phi(m)}\equiv 1(mod
\ m)$ where $\phi$ is Euler's $\phi$-function.  We start by proving
a theorem about the inverse of integers modulo primes.

\begin{theorem}
Let $p$ be a prime.  A positive integer $m$ is its own inverse
modulo $p$ if and only if $p$ divides $m+1$ or $p$ divides $m-1$.
\end{theorem}

\begin{proof}
Suppose that $m$ is its own inverse.  Thus
\begin{equation*}
m.m\equiv 1(mod \ p).
\end{equation*}
Hence $p\mid m^2-1$.  As a result,
\begin{equation*}
p\mid (m-1) \mbox{or} \ \  p\mid (m+1).
\end{equation*}
We get that $m\equiv 1(mod\ p)$ or $m\equiv -1 (mod \ p)$.
\par Conversely, suppose that
\begin{equation*}
m\equiv 1(mod\ p) \mbox{or} \ \  m\equiv -1 (mod \ p).
\end{equation*}
Thus
\begin{equation*}
m^2\equiv 1(mod \ p).
\end{equation*}
\end{proof}
\index{Wilson's Theorem}
\begin{theorem}\textbf{Wilson's Theorem}
If $p$ is a prime number, then $p$ divides $(p-1)!+1$.
\end{theorem}

\begin{proof}
When $p=2$, the congruence holds.  Now let $p>2$.  Using Theorem 26,
we see that for each $1\leq m\leq p$, there is an inverse $1\leq
\bar{m}\leq p$ such that $m\bar{m}\equiv 1(mod \ p)$.  Thus by
Theorem 28, we see that the only two integers that have their own
inverses are $1$ and $p-1$. Hence after coupling the integers from 2
to $p-2$ each with its inverse, we get
\begin{equation*}
2.3.....(p-2)\equiv 1(mod \ p).
\end{equation*}
Thus we get
\begin{equation*}
1.2.3.....(p-2)(p-1)\equiv (p-1)(mod \ p)
\end{equation*}
As a result, we have $(p-1)!\equiv -1(mod \ p)$.
\end{proof}

Note also that the converse of Wilson's theorem also holds.  The
converse tells us whether an integer is prime or not.

\begin{theorem}
If $m$ is a positive integer with $m\geq 2$ such that
\begin{equation*}
(m-1)!+1\equiv 0 \ (mod \ m)
\end{equation*}
then $m$ is prime.
\end{theorem}
\begin{proof}
Suppose that $m$ has a proper divisor $c_1$ and that
\begin{equation*}
(m-1)!+1\equiv 0(mod \ m).
\end{equation*}
That is $m=c_1c_2$ where $1<c_1<m$ and $1<c_2<m$.  Thus $c_1$ is a
divisor of $(m-1)!$. Also, since
\begin{equation*}
m\mid ((m-1)!+1),
\end{equation*}
we get
\begin{equation*}
c_1\mid ((m-1)!+1).
\end{equation*}
As a result, by Theorem 4, we get that
\begin{equation*}
c_1\mid ((m-1)!+1-(m-1)!),
\end{equation*}
which gives that $c_1\mid 1$.  This is a contradiction and hence $m$
is prime.
\end{proof}

We now present Fermat's Theorem or what is also known as Fermat's
Little Theorem.  It states that the remainder of $a^{p-1}$  when
divided by a prime $p$ that doesn't divide $a$ is 1. We then state
Euler's theorem which states that the remainder of $a^{\phi(m)}$
when divided by a positive integer $m$ that is relatively prime to
$a$ is 1. We prove Euler's Theorem only because Fermat's Theorem is
nothing but a special case of Euler's Theorem. This is due to the
fact that for a prime number $p$, $\phi(p)=p-1$. \index{Euler's
Theorem}
\begin{theorem}\textbf{Euler's Theorem}
If $m$ is a positive integer and $a$ is an integer such that
$(a,m)=1$, then
\begin{equation*}
a^{\phi(m)}\equiv 1(mod \ m)
\end{equation*}
\end{theorem}

\begin{example}
Note that $3^4=81 \equiv 1(mod \ 5)$. Also,
$2^{\phi(9)}=2^6=64\equiv 1(mod \ 9)$.
\end{example}

We now present the proof of Euler's theorem.

\begin{proof}
Let $k_1,k_2,...,k_{\phi(m)}$ be a reduced residue system modulo
$m$. By Theorem 25, the set
\begin{equation*}
\{ak_1,ak_2,...,ak_{\phi(m)}\}
\end{equation*}
also forms a reduced residue system modulo $m$. Thus
\begin{equation*}
ak_1ak_2...ak_{\phi(m)}=a^{\phi(m)}k_1k_2...k_{\phi(m)}\equiv
k_1k_2...k_{\phi(m)}(mod \ m).
\end{equation*}
Now since $(k_i,m)=1$ for all $1\leq i\leq \phi(m)$, we have
$(k_1k_2...k_{\phi(m)},m)=1$.  Hence by Theorem 22 we can cancel the
product of $k$'s on both sides and we get
\begin{equation*}
a^{\phi(m)}\equiv 1(mod \ m).
\end{equation*}
\end{proof}

An immediate consequence of Euler's Theorem is: \index{Fermat's
Theorem}
\begin{cor}\textbf{Fermat's Theorem}
If p is a prime and $a$ is a positive integer with $p\nmid a$, then
\begin{equation*}
a^{p-1}\equiv 1(mod\ p).
\end{equation*}
\end{cor}


We now present a couple of theorems that are direct consequences of
Fermat's theorem.  The first states Fermat's theorem in a different
way.  It says that the remainder of $a^{p}$ when divided by $p$ is
the same as the remainder of $a$ when divided by $p$. The other
theorem determines the inverse of an integer $a$ modulo $p$ where
$p\nmid a$.

\begin{theorem}
If $p$ is a prime number and $a$ is a positive integer, then
$a^p\equiv a(mod \ p)$.
\end{theorem}

\begin{proof}
If $p\nmid a$, by Fermat's theorem we know that
\begin{equation*}
a^{p-1}\equiv 1(mod \ p).
\end{equation*}
Thus, we get
\begin{equation*}
a^{p}\equiv a(mod \ p).
\end{equation*}
Now if $p\mid a$, we have
\begin{equation*}
a^p\equiv a\equiv 0 (mod \ p).
\end{equation*}
\end{proof}

\begin{theorem}
If $p$ is a prime number and $a$ is an integer such that $p\nmid a$,
then $a^{p-2}$ is the inverse of a modulo $p$.
\end{theorem}

\begin{proof}
If $p\nmid a$, then Fermat's theorem says that
\begin{equation*}
a^{p-1}\equiv 1(mod\ p).
\end{equation*}
Hence
\begin{equation*}
a^{p-2}a\equiv 1(mod\ p).
\end{equation*}
As a result, $a^{p-2}$ is the inverse of $a$ modulo $p$.
\end{proof}

\textbf{Exercises}
\begin{enumerate}
\item{Show that 10!+1 is divisible by 11.}\item{What is the
remainder when 5!25! is divided by 31?}\item{What is the remainder
when $5^{100}$ is divided by 7?}\item{Show that if $p$ is an odd
prime, then $2(p-3)!\equiv -1(mod \ p)$.} \item{Find a reduced
residue system modulo $2^m$, where $m$ is a positive
integer.}\item{Show that if $a_1,a_2,...,a_{\phi(m)}$ is a reduced
residue system modulo $m$, where $m$ is a positive integer with
$m\neq 2$, then $a_1+a_2+...+a_{\phi(m)}\equiv 0 (mod \
m)$.}\item{Show that if $a$ is an integer such that $a$ is not
divisible by 3 or such that $a$ is divisible by 9, then $a^7\equiv a
(mod \ 63)$.}
\end{enumerate}





\chapter{Multiplicative Number Theoretic Functions}
In this chapter, we study functions, called multiplicative
functions, that are defined on integers. These functions have the
property that their value at the product of two relatively prime
integers is equal to the product of the value of the functions at
these integers.  We start by proving several theorems about
multiplicative functions that we will use later.  We then study
special functions and prove that the Euler $\phi$-function that was
seen before is actually multiplicative. We also define the sum of
divisors and the number of divisors functions.

\par Later define the Mobius function which investigate
integers in terms of their prime decomposition. The summatory
function of a given function takes the sum of the values of $f$ at
the divisors of a given integer $n$. We then determine the Mobius
inversion of this function which writes the values of $f$ in terms
of the values of its summatory function.  We end this chapter by
presenting integers with interesting properties and prove some of
their properties. \index{Decomposition}

\section{Definitions and Properties} \index{Arithmetic Function}
\begin{definition}
An arithmetic function is a function whose domain of definition is the set $\mathbb{N}$ of positive integers.
\end{definition}
\index{Multiplicative Function}
\begin{definition}
An arithmetic function $f$ is called multiplicative if
$f(ab)=f(a)f(b)$ for all $a,b\in\mathbb{N}$ such that $(a,b)=1$.
\end{definition}

\begin{definition}
An arithmetic function $f$ is called completely multiplicative if
\begin{equation}
f(ab)=f(a)f(b)
\end{equation}
for all positive integers $a,b$.
\end{definition}
\index{Completely Multiplicative}
\begin{example}
The function $f(a)=1$ where $k$ is a completely multiplicative
function since
\begin{equation*}
f(ab)=1=f(a)f(b).
\end{equation*}
Notice also that a completely multiplicative function is a
multiplicative function but not otherwise.
\end{example}

We now prove a theorem about multiplicative functions.  We will be
interested in studying the properties of multiplicative functions
rather than the completely multiplicative ones.

\begin{theorem}
Given a multiplicative function $f$.  Let $n=\prod_{k=1}^sp_k^{a_k}$
be the prime factorization of $n$. Then
\begin{equation*}
f(n)=\prod_{k=1}^sf(p_k^{a_k}).
\end{equation*}
\end{theorem}

\begin{proof}
We prove this theorem by induction on the number of primes in the
factorization of $n$.  Suppose that $n=p_1^{a_1}$.  Thus the result
follow easily. Suppose now that for
\begin{equation*}
n=\prod_{k=1}^sp_k^{a_k},
\end{equation*}
we have
\begin{equation*}
f(n)=\prod_{k=1}^sf(p_k^{a_k}).
\end{equation*}
So we have to prove that if
\begin{equation*}
n=\prod_{k=1}^{s+1}p_k^{a_k},
\end{equation*}
then
\begin{equation*}
f(n)=\prod_{k=1}^{s+1}f(p_k^{a_k}).
\end{equation*}
Notice that for
\begin{equation*}
n=\prod_{k=1}^{s+1}p_k^{a_k},
\end{equation*}
we have $(\prod_{k=1}^{s}p_k^{a_k},p_{s+1}^{a_{s+1}})=1$. Thus we
have get
\begin{equation*}
f(n)=f(\prod_{k=1}^{s+1}p_k^{a_k})=f(\prod_{k=1}^{s}p_k^{a_k})f(p_{s+1}^{a_{s+1}})
\end{equation*}
which by the inductive step gives
\begin{equation*}
f(\prod_{k=1}^{s+1}p_k^{a_k})=f(n)=\prod_{k=1}^{s+1}f(p_k^{a_k}).
\end{equation*}
\end{proof}

From the above theorem, we can see that to evaluate a multiplicative
function at an integer, it will be enough to know the value of the
function at the primes that are in the prime factorization of the
number.

\par We now define summatory functions which represents the sum of
the values of a given function at the divisors of a given number.

\begin{definition}
Let $f$ be an arithmetic function.  Define
\begin{equation*}
F(n)=\sum_{d\mid n}f(d)
\end{equation*}
Then $F$ is called the summatory function of $f$. \index{Summatory
Function}
\end{definition}
This function determines the sum of the values of the arithmetic
function at the divisors of a given integer.
\begin{example}
If $f(n)$ is an arithmetic function, then
\begin{equation*}
F(18)=\sum_{d\mid 18}f(d)=f(1)+f(2)+f(3)+f(6)+f(9)+f(18).
\end{equation*}
\end{example}

\begin{theorem}
If $f$ is a multiplicative function, then the summatory function of
$f$ denoted by $F(n)=\sum_{d\mid n}f(d)$ is also multiplicative.
\end{theorem}

\begin{proof}
We have to prove that $F(mn)=F(m)F(n)$ whenever $(m,n)=1$.  We have
\begin{equation*}
F(mn)=\sum_{d\mid mn}f(d).
\end{equation*}
Notice that by Lemma 6, each divisor of $mn$ can be written uniquely
as a product of relatively prime divisors $d_1$ of $m$
 and $d_2$ of $n$, moreover the product of any two divisors of $m$
 and $n$ is a divisor of $mn$.  Thus we get
 \begin{equation*}
 F(mn)=\sum_{d_1\mid m, d_2\mid n}f(d_1d_2)
 \end{equation*}
 Notice that since $f$ is multiplicative, we have
 \begin{eqnarray*}
F(mn)&=& \sum_{d_1\mid m, d_2\mid n}f(d_1d_2)\\&=&\sum_{d_1\mid m,
d_2\mid n}f(d_1)f(d_2)\\&=&\sum_{d_1\mid m}f(d_1)\sum_{d_2\mid n}
f(d_2)=F(m)F(n)
 \end{eqnarray*}
\end{proof}

\textbf{Exercises}
\begin{enumerate}
\item{Determine whether the arithmetic functions $f(n)=n!$ and
$g(n)=n/2$ are completely multiplicative or not.} \item{Define the
arithmetic function $g(n)$ by the following.  g(n)=1 if $n=1$ and 0
for $n>1$. Prove that $g(n)$ is multiplicative.}
\end{enumerate}


\section{Multiplicative Number Theoretic Functions}
\par We now present several multiplicative number theoretic
functions which will play a crucial role in many number theoretic
results. We start by discussing the Euler phi-function which was
defined in an earlier chapter.  We then define the sum-of-divisors
function and the number-of-divisors function along with their
properties.

\subsection{\textbf{The Euler $\phi$-Function}}
As defined earlier, the Euler $\phi$-function counts the number of
integers smaller than and relatively prime to a given integer. We
first calculate the value of the $phi$-function at primes and prime
powers.

\begin{theorem}
If $p$ is prime, then $\phi(p)=p-1$. Conversely, if $p$ is an
integer such that $\phi(p)=p-1$, then $p$ is prime.
\end{theorem}

\begin{proof}
The first part is obvious since every positive integer less than $p$
is relatively prime to $p$.  Conversely, suppose that $p$ is not
prime.  Then $p=1$ or $p$ is a composite number.  If $p=1$, then
$\phi(p)\neq p-1$.  Now if $p$ is composite, then $p$ has a positive
divisor.  Thus $\phi(p)\neq p-1$. We have a contradiction and thus
$p$ is prime.
\end{proof}

We now find the value of $\phi$ at prime powers.

\begin{theorem}
Let $p$ be a prime and $m$ a positive integer, then
$\phi(p^m)=p^m-p^{m-1}$.
\end{theorem}

\begin{proof}
Note that all integers that are relatively prime to $p^m$ and that
are less than $p^m$ are those that are not multiple of $p$. Those
integers are $p,2p,3p,...,p^{m-1}p$.  There are $p^{m-1}$ of those
integers that are not relatively prime to $p^m$ and that are less
than $p^m$.  Thus
\begin{equation*}
\phi(p^m)=p^m-p^{m-1}.
\end{equation*}
\end{proof}

\begin{example}
$\phi(7^3)=7^3-7^2=343-49=294$.  Also $\phi(2^{10})=2^{10}-2^9=512.$
\end{example}

We now prove that $\phi$ is a multiplicative function.

\begin{theorem}
Let $m$ and $n$ be two relatively prime positive integers.  Then
$\phi(mn)=\phi(m)\phi(n)$.
\end{theorem}

\begin{proof}
Denote $\phi(m)$ by $s$ and let $k_1,k_2,...,k_s$ be a reduced
residue system modulo $m$.  Similarly, denote $\phi(n)$ by $t$ and
let $k_1',k_2',...,k_t'$ be a reduced residue system modulo $n$.
Notice that if $x$ belongs to a reduced residue system modulo $mn$,
then
\begin{equation*}
(x,m)=(x,n)=1.
\end{equation*}
Thus
\begin{equation*}
x\equiv k_i(mod\ m) \mbox{and} \ \  x\equiv k_j'(mod \ n)
\end{equation*}
for some $i,j$. Conversely, if
\begin{equation*}
x\equiv k_i(mod\ m) \mbox{and} \ \  x\equiv k_j'(mod \ n)
\end{equation*}
some $i,j$ then $(x,mn)=1$ and thus $x$ belongs to a reduced residue
system modulo $mn$. Thus a reduced residue system modulo $mn$ can be
obtained by by determining all $x$ that are congruent to $k_i$ and
$k_j'$ modulo $m$ and $n$ respectively.  By the Chinese remainder
theorem, the system of equations
\begin{equation*}
x\equiv k_i(mod\ m) \mbox{and} \ \  x\equiv k_j'(mod \ n)
\end{equation*}
has a unique solution. Thus different $i$ and $j$ will yield
different answers. Thus $\phi(mn)=st$.
\end{proof}

We now derive a formula for $\phi(n)$.

\begin{theorem}
Let $n=p_1^{a_1}p_2^{a_2}...p_s^{a_s}$ be the prime factorization of
$n$.  Then
\begin{equation*}
\phi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...\left(1-\frac{1}{p_s}\right).
\end{equation*}
\end{theorem}

\begin{proof}
By Theorem 37, we can see that for all $1\leq i\leq k$
\begin{equation*}
\phi(p_i^{a_i})=p_i^{a_i}-p_i^{a_i-1}=p_i^{a_i}\left(1-\frac{1}{p_i}\right).
\end{equation*}
Thus by Theorem 38,
\begin{eqnarray*}
\phi(n)&=&\phi(p_1^{a_1}p_2^{a_2}...p_s^{a_s})\\&=&
\phi(p_1^{a_1})\phi(p_2^{a_2})...\phi(p_s^{a_s})\\&=&p_1^{a_1}\left(1-\frac{1}{p_1}\right)
p_2^{a_2}\left(1-\frac{1}{p_2}\right)...p_s^{a_s}\left(1-\frac{1}{p_s}\right)\\&=&
p_1^{a_1}p_2^{a_2}...p_k^{a_k}\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...
\left(1-\frac{1}{p_s}\right)\\&=&
n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...\left(1-\frac{1}{p_s}\right).
\end{eqnarray*}
\end{proof}

\begin{example}
Note that
\begin{equation*}
\phi(200)=\phi(2^35^2)=200\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)=80.
\end{equation*}
\end{example}

\begin{theorem}
Let $n$ be a positive integer greater than 2.  Then $\phi(n)$ is
even.
\end{theorem}

\begin{proof}
Let $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$.  Since $\phi$ is
multiplicative, then
\begin{equation*}
\phi(n)=\prod_{j=1}^k\phi(p_j^{a_j}).
\end{equation*}
Thus by Theorem 39, we have
\begin{equation*}
\phi(p_j^{a_j})=p_j^{a_j-1-1}(p_j-1).
\end{equation*}
We see then $\phi(p_j^{a_j})$is even if $p_j$ is an odd prime.
Notice also that if $p_j=2$, then it follows that $\phi(p_j^{a_j})$
is even.  Hence $\phi(n)$ is even.
\end{proof}

\begin{theorem}
Let $n$ be a positive integer.  Then
\begin{equation*}
\sum_{d\mid n}\phi(d)=n.
\end{equation*}
\end{theorem}

\begin{proof}
Split the integers from 1 to $n$ into classes.  Put an integer $m$
in the class $C_d$ if the greatest common divisor of $m$ and $n$
is $d$.  Thus the number of integers in the $C_d$ class is the
number of positive integers not exceeding $n/d$ that are relatively
prime to n/d.  Thus we have $\phi(n/d)$ integers in $C_d$.  Thus we
see that
\begin{equation*}
n=\sum_{d\mid n}\phi(n/d).
\end{equation*}
As $d$ runs over all divisors of $n$, so does $n/d$.  Hence
\begin{equation*}
n=\sum_{d\mid n}\phi(n/d)=\sum_{d\mid n}\phi(d).
\end{equation*}
\end{proof}

\subsection{\textbf{The Sum-of-Divisors Function}}
The sum of divisors function, denoted by $\sigma(n)$, is the sum of
all positive divisors of $n$. \index{The Sum of Divisors Function}
\begin{example}
$\sigma(12)=1+2+3+4+6+12=28.$
\end{example}

Note that we can express $\sigma(n)$ as $\sigma(n)=\sum_{d\mid n}d$.
\par We now prove that $\sigma(n)$ is a multiplicative function.

\begin{theorem}
The sum of divisors function $\sigma(n)$ is multiplicative.
\end{theorem}

\begin{proof}
We have proved in Theorem 35 that the summatory function is
multiplicative once $f$ is multiplicative.  Thus let $f(n)=n$ and
notice that $f(n)$ is multiplicative.  As a result, $\sigma(n)$ is
multiplicative.
\end{proof}

Once we found out that $\sigma(n)$ is multiplicative, it remains to
evaluate $\sigma(n)$ at powers of primes and hence we can derive a
formula for its values at any positive integer.

\begin{theorem}
Let $p$ be a prime and let $n=p_1^{a_1}p_2^{a_2}...p_t^{a_t}$ be a
positive integer. Then
\begin{equation*}
\sigma(p^a)=\frac{p^{a+1}-1}{p-1},
\end{equation*}
and as a result,
\begin{equation*}
\sigma(n)=\prod_{j=1}^{t}\frac{p_j^{a_j+1}-1}{p_j-1}
\end{equation*}
\end{theorem}

\begin{proof}
Notice that the divisors of $p^{a}$ are $1,p,p^2,...,p^a$. Thus
\begin{equation*}
\sigma(p^a)=1+p+p^2+...+p^a=\frac{p^{a+1}-1}{p-1}.
\end{equation*}
where the above sum is the sum of the terms of a geometric
progression.
\par Now since $\sigma(n)$ is multiplicative, we have
\begin{eqnarray*}
\sigma(n)&=&\sigma(p^{a_1})\sigma(p^{a_2})...\sigma(p^{a_t})\\&=&
\frac{p_1^{a_1+1}-1}{p_1-1}.\frac{p_2^{a_2+1}-1}{p_2-1}...\frac{p_t^{a_t+1}-1}{p_t-1}\\
&=&\prod_{j=1}^{t}\frac{p_j^{a_j+1}-1}{p_j-1}
\end{eqnarray*}
\end{proof}

\begin{example}
$\sigma(200)=\sigma(2^35^2)=\frac{2^4-1}{2-1}\frac{5^3-1}{5-1}=15.31=465.$
\end{example}

\subsection{\textbf{The Number-of-Divisors Function}}
The number of divisors function, denoted by $\tau(n)$, is the sum of
all positive divisors of $n$. \index{The Number of Divisor Function}
\begin{example}
$\tau(8)=4.$
\end{example}

We can also express $\tau(n)$ as $\tau(n)=\sum_{d\mid n}1$.
\par We can also prove that $\tau(n)$ is a multiplicative function.

\begin{theorem}
The number of divisors function $\tau(n)$ is multiplicative.
\end{theorem}

\begin{proof}
By Theorem 36, with $f(n)=1$, $\tau(n)$ is multiplicative.
\end{proof}

We also find a formula that evaluates $\tau(n)$ for any integer $n$.

\begin{theorem}
Let $p$ be a prime and let $n=p_1^{a_1}p_2^{a_2}...p_t^{a_t}$ be a
positive integer. Then
\begin{equation*}
\tau(p^a)=a+1,
\end{equation*}
and as a result,
\begin{equation*}
\tau(n)=\prod_{j=1}^{t}(a_j+1).
\end{equation*}
\end{theorem}

\begin{proof}
The divisors of $p^{a}$ as mentioned before are $1,p,p^2,...,p^a$.
Thus
\begin{equation*}
\tau(p^a)=a+1
\end{equation*}
\par Now since $\tau(n)$ is multiplicative, we have
\begin{eqnarray*}
\tau(n)&=&\tau(p^{a_1})\tau(p^{a_2})...\tau(p^{a_t})\\&=&
(a_1+1)(a_2+1)...(a_t+1)\\
&=&\prod_{j=1}^{t}(a_j+1).
\end{eqnarray*}
\end{proof}

\begin{example}
$\tau(200)=\tau(2^35^2)=(3+1)(2+1)=12$.
\end{example}

\textbf{Exercises}
\begin{enumerate}
\item{Find $\phi(256)$ and $\phi(2.3.5.7.11)$.} \item{Show that
$\phi(5186)=\phi(5187)$.}\item{Find all positive integers $n$ such
that $\phi(n)=6$.}\item{Show that if $n$ is a positive integer, then
$\phi(2n)=\phi(n)$ if $n$ is odd.} \item{Show that if $n$ is a
positive integer, then $\phi(2n)=2\phi(n)$ if $n$ is
even.}\item{Show that if $n$ is an odd integer, then
$\phi(4n)=2\phi(n)$.}\item{Find the sum of positive integer divisors
and the number of positive integer divisors of 35}\item{Find the sum
of positive integer divisors and the number of positive integer
divisors of $2^53^45^37^313$}.\item{Which positive integers have an
odd number of positive divisors.}\item{Which positive integers have
exactly two positive divisors.}
\end{enumerate}


\section{The Mobius Function and the Mobius Inversion Formula}
We start by defining the Mobius function which investigates integers
in terms of their prime decomposition.  We then determine the Mobius
inversion formula which determines the values of the a function $f$
at a given integer in terms of its summatory function.

\begin{definition}
$\mu(n)=\left\{\begin{array}{lcr}
\ 1   \ \  \mbox{if}\ \  n=1;\\
\ (-1)^t  \ \  \mbox{if}\ \  n=p_1p_2...p_t \ \  \mbox{where the}\ \  p_i \ \   \mbox{are distinct primes};\\
\ 0   \ \  \mbox{ otherwise}.\\
\end{array}\right .\ $
\end{definition}

Note that if $n$ is divisible by a power of a prime higher than
one then $\mu(n)=0$.

In connection with the above definition, we have the following
\index{Square-Free}
\begin{definition}
An integer $n$ is said to be \bf{square-free}, if no square divides it, i.e. if there does not exist an integer $k$
such that $k^2\mid n$.
\end{definition}

It is immediate (prove as exercise) that the prime-number
factorization of a square-free integer contains only distinct
primes.

\begin{example}
Notice that $\mu(1)=1$, $\mu(2)=-1$, $\mu(3)=-1$ and $\mu(4)=0$.
\end{example}

We now prove that $\mu(n)$ is a multiplicative function.
\index{Mobius Function}
\begin{theorem}
The Mobius function $\mu(n)$ is multiplicative.
\end{theorem}

\begin{proof}
Let $m$ and $n$ be two relatively prime integers.  We have to prove
that
\begin{equation*}
\mu(mn)=\mu(m)\mu(n).
\end{equation*}
If $m=n=1$, then the equality holds. Also, without loss of
generality, if $m=1$, then the equality is also obvious.  Now
suppose that $m$ or $n$ is divisible by a power of prime higher than
1, then
\begin{equation*}
\mu(mn)=0=\mu(m)\mu(n).
\end{equation*}
What remains to prove that if $m$ and $n$ are square-free integers
say $m=p_1p_2...p_s$ where $p_1,p_2,...,p_s$ are distinct primes and
$n=q_1q_2...q_t$ where $q_1,q_2,...,q_t$.  Since $(m,n)=1$, then
there are no common primes in the prime decomposition between $m$
and $n$.  Thus
\begin{equation*}
\mu(m)=(-1)^s, \mu(n)=(-1)^t \mbox{and} \ \  \mu(mn)=(-1)^{s+t}.
\end{equation*}
\end{proof}

In the following theorem, we prove that the summatory function of
the Mobius function takes only the values $0$ or $1$.

\begin{theorem}
Let $F(n)=\sum_{d\mid n}\mu(d)$, then $F(n)$ satisfies
\begin{equation*}
F(n)=\left\{\begin{array}{lcr}
\ 1   \ \  \mbox{if}\ \  n=1;\\
\ 0  \ \  \mbox{if}\ \  n>1.\\
\end{array}\right .\
\end{equation*}
\end{theorem}

\begin{proof}
For $n=1$, we have $F(1)=\mu(1)=1$. Let us now find $\mu(p^k)$ for
any integer $k>0$.  Notice that
\begin{equation*}
F(p^k)=\mu(1)+\mu(p)+...+\mu(p^k)=1+(-1)+0+...+0=0
\end{equation*}
Thus by Theorem 36, for any integer
$n=p_1^{a_1}p_2^{a_2}...p_t^{a_t}>1$ we have,
\begin{equation*}
F(n)=F(p_1^{a_1})F(p_2^{a_2})...F(p_t^{a_t})=0
\end{equation*}
\end{proof}

We now define the Mobius inversion formula.  The Mobius inversion
formula expresses the values of $f$ in terms of its summatory
function of $f$. \index{Mobius Inversion Formula}
\begin{theorem}
Suppose that $f$ is an arithmetic function and suppose that $F$ is
its summatory function, then for all positive integers $n$ we have
\begin{equation*}
f(n)=\sum_{d\mid n}\mu(d)F(n/d).
\end{equation*}
\end{theorem}

\begin{proof}
We have
\begin{eqnarray*}
\sum_{d\mid n}\mu(d)F(n/d)&=&\sum_{d\mid n}\mu(d)\sum_{e\mid
(n/d)}f(e)\\ &=& \sum_{d\mid n}\sum_{e\mid
(n/d)}\mu(d)f(e)\\&=&\sum_{e\mid n}\sum_{d\mid
(n/e)}\mu(d)f(e)\\&=&\sum_{e\mid n}f(e)\sum_{d\mid
(n/d)}\mu(d)\\
\end{eqnarray*}
Notice that $\sum_{d\mid (n/e)}\mu(d)=0$ unless $n/e=1$ and thus
$e=n$.  Consequently we get
\begin{equation*}
\sum_{e\mid n}f(e)\sum_{d\mid (n/d)}\mu(d)=f(n).1=f(n).
\end{equation*}
\end{proof}

\begin{example}
A good example of a Mobius inversion formula would be the inversion
of $\sigma(n)$ and $\tau(n)$.  These two functions are the summatory
functions of $f(n)=n$ and $f(n)=1$ respectively. Thus we get
\begin{equation*}
n=\sum_{d\mid n}\mu(n/d)\sigma(d)
\end{equation*}
and
\begin{equation*}
1=\sum_{d\mid n}\mu(n/d)\tau(d).
\end{equation*}
\end{example}

\textbf{Exercises}
\begin{enumerate}
\item{Find $\mu(12)$, $\mu(10!)$ and $\mu(105)$.}\item{Find the
value of $\mu(n)$ for each integer $n$ with $100\leq n\leq
110$.}\item{Use the Mobius inversion formula and the identity
$n=\sum_{d\mid n}\phi(n/d)$ to show that $\phi(p^t)=p^t-p^{t-1}$
where $p$ is a prime and $t$ is a positive integer.}
\end{enumerate}



\section{Perfect, Mersenne, and Fermat Numbers}

Integers with certain properties were studied extensively over the
centuries.  We present some examples of such integers and prove
theorems related to these integers and their properties.

\par We start by defining perfect numbers.
\index{Perfect Numbers}
\begin{definition}
A positive integer $n$ is called a perfect number if $\sigma(n)=2n$.
\end{definition}

In other words, a perfect number is a positive integer which is the
sum of its proper divisors.

\begin{example}
The first perfect number is 6, since $\sigma(6)=12$. You can also
view this as $6=1+2+3$. The second perfect number is 28, since
$\sigma(28)=56$ or  $28=1+2+4+7+14$.
\end{example}

The following theorem tells us which even positive integers are
perfect.

\begin{theorem}
The positive integer $n$ is an even perfect number if and only if
\begin{equation*}
n=2^{l-1}(2^l-1),
\end{equation*}
where $l$ is an integer such that $l\geq 2$ and $2^l-1$ is prime.
\end{theorem}

\begin{proof}
We show first that if $n=2^{l-1}(2^l-1)$ where $l$ is an integer
such that $l\geq 2$ and $2^l-1$ is prime then $n$ is perfect. Notice
that $2^l-1$ is odd and thus $(2^{l-1},2^l-1)=1$.  Also, notice that
$\sigma$ is a multiplicative function and thus
\begin{equation*}
\sigma(n)=\sigma(2^{l-1})\sigma(2^l-1).
\end{equation*}
Notice that $\sigma(2^{l-1})=2^l-1$ and since $ 2^l-1$ is prime we
get $\sigma(2^l-1)=2^l$.  Thus
\begin{equation*}
\sigma(n)=2n.
\end{equation*}
We now prove the converse.  Suppose that $n$ is a perfect number.
Let $n=2^rs$, where $r$ and $s$ are positive integers and $s$ is
odd. Since $(2^r,s)=1$, we get
\begin{equation*}
\sigma(n)=\sigma(2^r)\sigma(s)=(2^{r+1}-1)\sigma(s).
\end{equation*}
Since $n$ is perfect, we get
\begin{equation*}
(2^{r+1}-1)\sigma(s)=2^{r+1}s.
\end{equation*}
Notice now that $(2^{r+1}-1, 2^{r+1})=1$ and thus $2^{r+1}\mid
\sigma(s)$. Therefore there exists an integer $q$ such that
$\sigma(s)=2^{r+1}q$.  As a result, we have
\begin{equation*}
(2^{r+1}-1)2^{r+1}q=2^{r+1}s
\end{equation*}
and thus we get
\begin{equation*}
(2^{r+1}-1)q=s
\end{equation*}
So we get that $q\mid s$.  We add $q$ to both sides of the above
equation and we get
\begin{equation*}
s+q=(2^{r+1}-1)q+q=2^{r+1}q=\sigma(s).
\end{equation*}
We have to show now that $q=1$.  Notice that if $q\neq 1$, then $s$
will have three divisors and thus $\sigma(s)\geq 1+s+q$. Hence $q=1$
and as a result $s=2^{r+1}-1$.  Also notice that $\sigma(s)=s+1$.
This shows that $s$ is prime since the only divisors of $s$ are $1$
and $s$.  As a result,
\begin{equation*}
n=2^r(2^{r+1}-1),
\end{equation*}
where $(2^{r+1}-1)$ is prime.
\end{proof}

In theorem 50, we see that to determine even perfect numbers, we
need to find primes of the form $2^l-1$.  It is still unknown
whether there are odd perfect numbers or not.

\begin{theorem}
If $2^l-1$ is prime where $l$ is a positive integer, then $l$ must
be prime.
\end{theorem}

\begin{proof}
Suppose that $l$ is composite, that is $l=rs$ where $1<r<m$ and
$1<s<m$.  Thus after factoring, we get that
\begin{equation*}
2^m-1=(2^r-1)(2^{r(s-1)}+2^{r(s-2)}+...+2^{r}+1)
\end{equation*}
Notice that the two factors above are both greater than 1.  Thus
$2^m-1$ is not prime.  This is a contradiction.
\end{proof}
The above theorem motivates the definition of interesting numbers
called Mersenne numbers. \index{Mersenne Numbers} \index{Mersenne
Primes}
\begin{definition}
Let $l$ be a positive integer.  An integer of the form $M_l=2^l-1$
is called the $l$th Mersenne number; if $l$ is prime then
$M_l=2^l-1$ is called the $l$th Mersenne prime.
\end{definition}

\begin{example}
$M_3=2^3-1=7$ is the third Mersenne prime.
\end{example}

We prove a theorem that help decide whether Mersenne numbers are
prime.

\begin{theorem}
Divisors of $M_p=2^p-1$ for prime $p$ is of the form $2mp+1$, where
$m$ is a positive integer.
\end{theorem}

\begin{proof}
Let $p_1$ be a prime dividing $M_p=2^p-1$.  By Fermat's theorem, we
know that $p_1\mid (2^{p_1-1}-1)$.  Also, it is easy to see that
\begin{equation*}
(2^{p}-1,2^{p_1-1}-1)=2^{(p,p_1-1)}-1.
\end{equation*}
Since $p_1$ is a common divisor of $2^p-1$ and $2^{p_1-1}-1$ and
thus not relatively prime.  Hence $(p,p_1-1)=p$.  Hence $p\mid
(p_1-1)$ and thus there exists a positive integer $k$ such that
$p_1-1=kp$. Since $p_1$ is odd, then $k$ is even and thus $k=2m$.
Hence
\begin{equation*}
p_1=kp+1=2mp+1.
\end{equation*}
Because any divisor of $M_p$ is a product of prime divisors of
$M_p$, each prime divisor of $M_p$ is of the form $2mp+1$ and the
result follows.
\end{proof}

\begin{example}
$M_{23}=2^{23}-1$ is divisible by $47=46k+1$.  We know this by trial
and error and thus looking at all primes of the form $46k+1$ that
are less than $\sqrt{M_{23}}$.
\end{example}

We now define Fermat numbers and prove some theorems about the
properties of these numbers. \index{Fermat Numbers}
\begin{definition}
Integers of the form $F_n=2^{2^n}+1$ are called Fermat numbers.
\end{definition}

Fermat conjectured that these integers are primes but it turned out
that this is not true.  Notice that $F_0=3$, $F_1=5$, $F_2=17$,
$F_3=257$ and $F_4=65,537$ while $F_5$ is composite. It turned out
the $F_5$ is divisible by $641$.  We now present a couple of
theorems about the properties of these numbers.

\begin{theorem}
For all positive integers $n$, we have
\begin{equation*}
F_0F_1F_2...F_{n-1}=F_n-2
\end{equation*}
\end{theorem}

\begin{proof}
We will prove this theorem by induction.  For $n=1$, the above
identity is true.  Suppose now that
\begin{equation*}
F_0F_1F_2...F_{n-1}=F_n-2
\end{equation*}
holds.  We claim that
\begin{equation*}
F_0F_1F_2...F_{n}=F_{n+1}-2.
\end{equation*}
Notice that
\begin{equation*}
F_0F_1F_2...F_{n}=(F_n-2)F_n=(2^{2^n}-1)(2^{2^n}+1)=2^{2^{n+1}}-1=F_{n+1}-2.
\end{equation*}
\end{proof}
Using Theorem 53, we prove that Fermat numbers are relatively prime.

\begin{theorem}
Let $s \neq t$ be nonnegative integers.  Then $(F_s,F_t)=1$.
\end{theorem}

\begin{proof}
Assume without loss of generality that $s<t$.  Thus by Theorem 52,
we have
\begin{equation*}
F_0F_1F_2...F_s...F_{t-1}=F_t-2
\end{equation*}
Assume now that there is a common divisor $d$ of $F_s$ and $F_t$.
thus we see that $d$ divides
\begin{equation*}
F_t-F_0F_1F_2...F_s...F_{t-1}=2.
\end{equation*}
Thus $d=1$ or $d=2$.  But since $F_t$ is odd for all $t$.  We have
$d=1$. Thus $F_s$ and $F_t$ are relatively prime.
\end{proof}
\textbf{Exercises}
\begin{enumerate}
\item{Find the six smallest even perfect numbers.}\item{Find the
eighth perfect number.}\item{Find a factor of $2^{1001}-1$.}\item{We
say $n$ is abundant if $\sigma(n)>2n$. Prove that if
$n=2^{m-1}(2^m-1)$ where $m$ is a positive integer such that $2^m-1$
is composite, then $n$ is abundant.}\item{Show that there are
infinitely many even abundant numbers.}\item{Show that there are
infinitely many odd abundant numbers.}\item{Determine whether
$M_{11}$ is prime.}\item{Determine whether $M_{29}$ is
prime.}\item{Find all primes of the form $2^{2^n}+5$ where $n$ is a
nonnegative integer.}
\end{enumerate}







\chapter{Primitive Roots and Quadratic Residues}
 \par  In this chapter, we discuss the multiplicative
structure of the integers modulo $n$.  We introduce the concept of
the order of integer modulo $n$ and then we study its properties. We
then define primitive roots modulo $n$ and show how to determine
whether an integer is primitive modulo $n$ or not.  We later find
all positive integers having primitive roots and prove related
results.

\par We define the concept of a quadratic residue and establish
its basic properties.  We then introduce Legendre symbol and also
develop its basic properties.  We also introduce the law of
quadratic reciprocity.  Afterwards, we generalize the notion of
Legendre symbol to the Jacobi symbol and discuss the law of
reciprocity related to Jacobi symbol.

\section{The order of Integers and Primitive Roots}
In this section, we study the order of an integer modulo $n$, where
$n$ is positive.  We also define primitive roots and related
results.  Euler's theorem in Chapter 4 states that if a positive
integer $a$ is relatively prime to $n$, then $a^{\phi(n)}\equiv 1
(mod \ n)$.  Thus by the well ordering principle, there is a least
positive integer $x$ that satisfies this congruence $a^{x}\equiv 1
(mod \ n)$. \index{Order of Integers}
\begin{def1}
Let $(a,b)=1$.  The smallest positive integer $x$ such that $a^{x}
\equiv 1(mod \ b)$ is called the order of $a$ modulo $b$.  We denote
the order of $a$ modulo $b$ by $ord_ba$.
\end{def1}

\begin{example}
$ord_72=3$ since $2^3\equiv 1(mod \ 7)$ while $2^1\equiv 2(mod \ 7)$
and $2^2\equiv 4(mod \ 7)$.
\end{example}

To find all integers $x$ such that $a^x\equiv 1(mod \ b)$, we need
the following theorem.

\begin{theorem}
If $(a,b)=1$ with $b>0$, then the positive integer $x$ is a solution
of the congruence $a^x\equiv 1(mod \ b)$ if and only if $ord_ba\mid
x$.
\end{theorem}

\begin{proof}
Having $ord_ba\mid x$, then we have that $x=k.ord_ba$ for some
positive integer $k$. Thus
\begin{equation*}
a^x=a^{kord_ba}=(a^{ord_ba})^k\equiv 1(mod \ b).
\end{equation*}
Now if $a^x\equiv 1(mod \ b)$, we use the division algorithm to
write
\begin{equation*}
x=q ord_ba+r, \ \ \ 0\leq r<ord_ba.
\end{equation*}
Thus we see that
\begin{equation*}
a^x\equiv a^{qord_ba+r}\equiv (a^{ord_ba})^qa^r\equiv a^r (mod \ b).
\end{equation*}
Now since $a^x\equiv 1(mod \ b)$,we have $a^r\equiv 1(mod \ b)$.
Since $ord_ba$, we get $r=0$.  Thus $x=q.ord_ba$ and hence
$ord_ba\mid x$.
\end{proof}

\begin{example}
Since $ord_72=3$, then $2^{15}\equiv 1(mod \ 7)$ while 10 is not a
solution for $2^x\equiv 1 (mod \ 7)$.
\end{example}

\begin{theorem}
If $(a,b)=1$ with $b>0$, then
\begin{equation*}
a^i\equiv a^j(mod \ b)
\end{equation*}
where $i$ and $j$ are nonnegative integers, if and only if
\begin{equation*}
i\equiv j(mod \ ord_ba)
\end{equation*}
\end{theorem}

\begin{proof}
Suppose that
\begin{equation*}
 i\equiv j(mod \ ord_ba)\ \  \mbox{and}\ \  0\leq j\leq i.
\end{equation*}
 Then we
have $i-j=k.ord_ba$, where $k$ is a positive integer.  Hence
\begin{equation*}
a^i=a^{j+k.ord_ba}=a^j(a^{ord_ba})^k\equiv a^j (mod \ b).
\end{equation*}
Assume now that $a^i\equiv a^j(mod \ b)$ with $i\geq j$.  Thus we
have
\begin{equation*}
a^i\equiv a^ja^{i-j}\equiv a^j(mod \ b)
\end{equation*}
Since $(a,b)=1$, we have $(a^j,b)=1$ and thus by Theorem 22, we get
\begin{equation*}
a^{i-j}\equiv 1(mod \ b).
\end{equation*}
By theorem 54, we get that $ord_ba \mid (i-j)$ and hence $i\equiv
j(mod \ b)$.

\end{proof}
We introduce now primitive roots and discuss their properties.  We
are interested in integers whose order modulo another integer is
$\phi(b)$. In one of the exercises, one is asked to prove that if $a
$and $b$ are relatively prime then $ord_ba \mid \phi(b)$.
\index{Primitive Roots}
\begin{def1}
If $(r,m)=1$ with $m>0$ and if $ord_mr=\phi(m)$ then $r$ is called a
primitive root modulo $m$.
\end{def1}

\begin{example}
Notice that $\phi(7)=6$ hence $2$ is not a primitive root modulo
$7$. While $ord_73=6$ and thus $3$ is a primitive root modulo $7$.
\end{example}

\begin{theorem}
If $(r,m)=1$ with $m>0$ and if $r$ is a primitive root modulo $n$,
then the integers $\{r^1,r^2,...r^{\phi(m)}\}$ form a reduced
residue set modulo $m$.
\end{theorem}

\begin{proof}
To prove that the set $\{r^1,r^2,...r^{\phi(m)}\}$ form a reduced
residue set modulo $m$ we need to show that every two of them are
relatively prime and that no two of them are congruent modulo $m$.
Since $(r,m)=1$, it follows that $(r^n,m)=1$ for all positive
integers $n$.  Hence all the powers of $r$ are relatively prime to
$m$.  To show that no two powers in the above set are equivalent
modulo $m$, assume that
\begin{equation*}
r^i\equiv r^j(mod \ m).
\end{equation*}
By Theorem 55, we see that
\begin{equation*}
i\equiv j(mod \ ord_m\phi(m)).
\end{equation*}
Notice that $1\leq i,j\leq \phi(m)$ and hence $i=j$.
\end{proof}

\begin{theorem}
If $ord_ma=t$ and if $u$ is a positive integer, then
\begin{equation*}
ord_m(a^u)=t/(t,u).
\end{equation*}
\end{theorem}

\begin{proof}
Let
\begin{equation*}
v=ord_m(a^u),\ \  w=(t,u), \ \ t=t_1w \mbox{and}\ \  u=u_1w.
\end{equation*}
Notice that $(t_1,u_1)=1.$
\par Because $t_1=t/(t,u)$, we want to show that $ord_m(a^u)=t_1$.
To do this, we will show that $(a^{u})^{t_1}\equiv 1(mod \ m)$ and
that if $(a^u)^v\equiv 1(mod \ m)$, then $t_1\mid v$.  First note
that
\begin{equation*}
(a^u)^{t_1}=(a^{u_1w})^{(t/w)}=(a^t)^{u_1}\equiv 1(mod \ m).
\end{equation*}
Hence by Theorem 54, we have $v\mid t_1$. Now on the other hand,
since
\begin{equation*}
(a^u)^v=a^{uv}\equiv 1(mod \ m),
\end{equation*}
we know that $t\mid uv$.  Hence $t_1w\mid u_1wv$ and hence $t_1\mid
u_1v$.  Because $(t_1,u_1)=1$, we see that $t_1\mid v$. Since $v\mid
t_1$ and $t_1\mid v$, we conclude that $v=t_1=t/w=t/(t,u)$.
\end{proof}

\begin{example}
We see that $ord_73^4=6/(6,4)$ since $ord_73=6$.
\end{example}

\begin{cor}
Let $r$ be a primitive root modulo $m$, where $m$ is a positive
integer, $m>1$. Then $r^u$ is a primitive root modulo $m$ if and
only if $(u,\phi(m))=1$.
\end{cor}

\begin{proof}
By Theorem 57, we see that
\begin{equation*}
ord_mr^u=ord_mr/(u,ord_mr)=\phi(m)/(u,\phi(m)).
\end{equation*}
Thus $ord_mr^u=\phi(m)$ and $r^u$ is a primitive root if and only if
$(u,\phi(m))=1$.
\end{proof}

The above corollary leads to the following theorem

\begin{theorem}
If the positive integer $m$ has a primitive root, then it has a
total of $\phi(\phi(m))$ incongruent primitive roots.
\end{theorem}

\begin{proof}
Let $r$ be a primitive root modulo $m$.  By Theorem 56, we see that
$\{r^1,r^2,...,r^{\phi(m)}\}$ form a reduced residue system modulo
$n$.  By Corollary 1, it is known that $r^u$ is a primitive root
modulo $m$ if and only if $(u,\phi(m))=1$.  Thus we have exactly
$\phi(\phi(m))$ such integers $u$ that are relatively prime to
$\phi(m)$ and hence there are exactly $\phi(\phi(m))$ primitive
roots modulo $m$.
\end{proof}

\textbf{Exercises}
\begin{enumerate}
\item{Determine $ord_{13}10$.}\item{Determine $ord_{11}3.$}\item{Show that 5 is a primitive root of
6.}\item{Show that if $\bar{a}$ is an inverse of $a$ modulo $n$,
then $ord_na=ord_n\bar{a}$.} \item{Show that if $n$ is a positive
integer, and $a$ and $b$ are integers relatively prime to $n$ such
that $(ord_na,ord_nb)=1$, then $ord_n(ab)=ord_na.ord_nb$.}\item{Show
that if $a$ is an integer relatively prime to the positive integer
$m$ and $ord_ma=st$, then $ord_ma^t=s$.}\item{Show that if $a$ and
$n$ are relatively prime with $n>0$, then $ord_na \mid \phi(n)$.}
\end{enumerate}

\section{Primitive Roots for Primes}
In this section, we show that every integer has a primitive root. To
do this we need to introduce polynomial congruence.
\par Let $f(x)$ be a polynomial with integer coefficients.  We say
that an integer $a$ is a root of $f(x)$ modulo $m$ if $f(a)\equiv 0
(mod\ m)$.

\begin{example}
Notice that $x\equiv 3 (mod\ 11)$ is a root for $f(x)=2x^2+x+1$
since $f(3)=22\equiv 0(mod \ 11)$.
\end{example}

We now introduce Lagrange's theorem for primes.  This is modulo p,
the fundamental theorem of algebra.  This theorem will be an
important tool to prove that every prime has a primitive root.
\index{Lagrange's Theorem}
\begin{theorem}\textbf{Lagrange's Theorem}
Let
\begin{equation*}
m(x)=b_nx^n+b_{n-1}x^{n-1}+...+b_1x+b_0
\end{equation*}
be a polynomial of degree $n, n\geq 1$ with integer coefficients and
with leading coefficient $b_n$ not divisible by a prime $p$.  Then
$m(x)$ has at most $n$ distinct incongruent roots modulo $p$.
\end{theorem}

\begin{proof}
Using induction, notice that if $n=1$, then we have
\begin{equation*}
m(x)=b_1x+b_0 \ \ \mbox{and} \ \ p \nmid b_1.
\end{equation*}
A root of $m(x)$ is a solution for $b_1x+b_0(mod \ p)$.  Since
$p\nmid b_1$, then this congruence has exactly one solution by
Theorem 26.
\par Suppose that the theorem is true for polynomials of degree
$n-1$, and let $m(x)$ be a polynomial of degree $n$ with integer
coefficients and where the leading coefficient is not divisible by
$p$.  Assume now that $m(x)$ has $n+1$ incongruent roots modulo $p$,
say $x_0,x_1,...,x_{n}$.  Thus
\begin{equation*}
m(x_k)\equiv 0(mod \ p)
\end{equation*}
for $0\leq k\leq n$. Thus we have
\begin{eqnarray*}
m(x)-m(x_0)&=&b_n(x^n-x_0^n)+b_{n-1}(x^{n-1}-x_0^{n-1})+...+b_1(x-x_0)
\\ &=&
b_n(x-x_0)(x^{n-1}+x^{n-2}x_0+...+xx_0^{n-2}+x_0^{n-1})\\&+&
b_{n-1}(x-x_0)(x^{n-2}+x^{n-3}x_0+...+xx_0^{n-3}+x_0^{n-2})+...+b_1(x-c_0)\\&=&
(x-x_0)f(x)
\end{eqnarray*}
where $f(x)$ is a polynomial of degree $n-1$ with leading
coefficient $b_n$.  Notice that since $m(x_k)\equiv m(x_0)(mod \
p)$, we have
\begin{equation*}
m(x_k)-m(x_0)=(x_k-x_0)f(x_k)\equiv 0(mod \ p).
\end{equation*}
Thus $f(x_k)\equiv 0(mod \ p)$ for all $1\leq k\leq n$ and thus
$x_1,x_2,...,x_n$ are roots of $f(x)$.  This is a contradiction
since we a have a polynomial of degree $n-1$ that has $n$ distinct
roots.
\end{proof}

We now use Lagrange's Theorem to prove the following result.

\begin{theorem}
Consider the prime $p$ and let $p-1=kn$ for some integer $k$. Then
$x^n-1$ has exactly $n$ incongruent roots modulo $p$.
\end{theorem}

\begin{proof}
Since $p-1=kn$, we have
\begin{eqnarray*}
x^{p-1}-1&=&(x^n-1)(x^{n(k-1)}+x^{n(k-2)}+...+x^n+1)
\\&=&(x^n-1)f(x)
\end{eqnarray*}
By Fermat's little theorem, we know that $x^{p-1}-1$ has $p-1$
incongruent roots modulo $p$.   Also, roots of $x^{p-1}-1$ are roots
of $f(x)$ or a root of $x^n-1$.  Notice that by Lagrange's Theorem,
we have that $f(x)$ has at most $p-n-1$ roots modulo $p$. Thus
$x^n-1$ has at least $n$ roots modulo $p$. But again by Lagrange's
Theorem, since we have that $x^n-1$ has at most $n$ roots, thus we
get that $x^n-1$ has exactly $n$ incongruent roots modulo $p$.
\end{proof}

We now prove a lemma that gives us how many incongruent integers can
have a given order modulo $p$.

\begin{lemma}
Let $p$ be a prime and let $m$ be a positive integer such that
$p-1=mk$ for some integer $k$. Then
$$S(m)=|\{m:0<m<p, \ \ m \in \mathbb{Z} \}|\leq \phi(m).$$
\end{lemma}

\begin{proof}
For each positive integer $m$ dividing $p-1$,
\par Notice that if $S(m)=0$, then $S(m)\leq \phi(m)$.  If
$S(m)>0$, then there is an integer $a$ of order $m$ modulo $p$.
Since $ord_pa=m$, then $a,a^2,...a^m$ are incongruent modulo $p$.
Also each power of $a$ is a root of $x^m-1$ modulo $p$ because
\begin{equation*}
(a^k)^m=(a^m)^k\equiv 1(mod \ p)
\end{equation*}
for all positive integers $k$. By Theorem 60, we know that $x^m-1$
has exactly $m$ incongruent roots modulo $p$, so that every root is
congruent to one of these powers of $a$.  We also know by Theorem 57
that the powers of $a^k$ with $(k,m)=1$ have order $m$.  There are
exactly $\phi(m)$ such integers with $1\leq k \leq m$ and thus if
there is one element of order $m$ modulo $p$, there must be exactly
$\phi(m)$ such positive integers less than $p$.  Hence $S(m)\leq
\phi(m)$.
\end{proof}

In the following theorem, we determine how many incongruent integers
can have a given order modulo $p$. We actually show the existence of
primitive roots for prime numbers.

\begin{theorem}
Every prime number has a primitive root.
\end{theorem}

\begin{proof}
Let $p$ be a prime and let $m$ be a positive integer such that
$p-1=mk$ for some integer $k$. Let $F(m)$ be the number of positive
integers of order $m$ modulo $p$ that are less than $p$. The order
modulo $p$ of an integer not divisible by $p$ divides $p-1$, it
follows that
\begin{equation*}
p-1=\sum_{m\mid p-1}F(m).
\end{equation*}
By Theorem 42, we see that
\begin{equation*}
p-1=\sum_{m\mid p-1}\phi(m).
\end{equation*}
By Lemma 1, $F(m)\leq \phi(m)$ when $m\mid (p-1)$.  Together with
\begin{equation*}
\sum_{m\mid p-1}F(m)=\sum_{m\mid p-1}\phi(m)
\end{equation*}
we see that $F(m)=\phi(m)$ for each positive divisor $m$ of $p-1$.
Thus we conclude that $F(m)=\phi(m)$. As a result, we see that there
are $p-1$ incongruent integers of order $p-1$ modulo $p$. Thus $p$
has $\phi(p-1)$ primitive roots.
\end{proof}

\textbf{Exercises}
\begin{enumerate}
\item{Find the incongruent roots modulo 11 of $x^2+2$.}\item{Find
the incongruent roots modulo 11 of $x^4+x^2+1$.}\item{Find the
incongruent roots modulo 13 of $x^3+12$.}\item{Find the number of
primitive roots of 13 and of 47.}\item{Find a complete set of
incongruent primitive roots of 13.}\item{Find a complete set of
incongruent primitive roots of 17.}\item{Find a complete set of
incongruent primitive roots of 19.}\item{Let $r$ be a primitive root
of $p$ with $p\equiv 1(mod \ 4)$.  Show that $-r$ is also a
primitive root.}\item{Show that if $p$ is a prime and $p\equiv 1(mod
\ 4)$, then there is an integer $x$ such that $x^2\equiv -1(mod \
p)$.}
\end{enumerate}

\section{The Existence of Primitive Roots}
In this section, we demonstrate which integers have primitive roots.
We start by showing that every power of an odd prime has a primitive
root and to do this we start by showing that every square of an odd
prime has a primitive root.

\begin{theorem}
If $p$ is an odd prime with primitive root $r$, then one can have
either $r$ or $r+p$ as a primitive root modulo $p^2$.
\end{theorem}

\begin{proof}
Notice that since $r$ is a primitive root modulo $p$, then
\begin{equation*}
ord_pr=\phi(p)=p-1.
\end{equation*}
Let $m=ord_{p^2}r$, then
\begin{equation*}
r^m\equiv 1(mod \ p^2).
\end{equation*}
Thus
\begin{equation*}
r^m\equiv 1(mod \ p).
\end{equation*}
By Theorem 54, we have
\begin{equation*}
p-1\mid m.
\end{equation*}
By Exercise 7 of section 6.1, we also have that
\begin{equation*}
m\mid \phi(p^2).
\end{equation*}
Also, $\phi(p^2)=p(p-1)$ and thus $m$ either divides $p$ or $p-1$.
And since $p-1\mid m$ then we have
\begin{equation*}
m=p-1 \ \ \mbox{or} \ \ m=p(p-1).
\end{equation*}
If $m=p(p-1)$ and $ord_{p^2}r=\phi(p^2)$ then $r$ is a primitive
root modulo $p^2$. Otherwise, we have $m=p-1$ and thus
\begin{equation*}
r^{p-1}\equiv 1(mod \ p^2).
\end{equation*}
Let $s=r+p$.  Then $s$ is also a primitive root modulo $p$.  Hence,
$ord_{p^2}s$ equals either $p-1$ or $p(p-1)$. We will show that
$ord_{p^2}s\neq p-1$ so that $ord_{p^2}s=p(p-1)$. Note that
\begin{eqnarray*}
s^{p-1}=(r+p)^{p-1}&=&r^{p-1}+(p-1)r^{p-2}p+...+p^{p-1}\\&=&
r^{p-1}+(p-1)p.r^{p-2}(mod \ p^2).
\end{eqnarray*}
Hence
\begin{equation*}
p^2\mid s^{p-1}-(1-pr^{p-2}.
\end{equation*}
Note also that if
\begin{equation*}
p^2 \mid (s^{p-1}-1),
\end{equation*}
 then
\begin{equation*}
p^2\mid pr^{p-2}.
\end{equation*}
Thus we have
\begin{equation*}
p\mid r^{p-2}
\end{equation*}
which is impossible because $p\nmid r$. Because $ord_{p^2}s\neq
p-1$, we can conclude that
\begin{equation*}
ord_{p^2}s=p(p-1)=\phi(p^2).
\end{equation*}
Thus, $s=r+p$ is a primitive root of $p^2$.
\end{proof}

\begin{example}
Notice that 7 has 3 as a primitive root. Either $ord_{49}3=6$ or
$ord_{49}3=42$.  But since $3^6\not\equiv 1(mod \ 49)$.  Hence
$ord_{49}3=42$.  Hence 3 is a primitive root of 49.
\end{example}

We now show that any power of an odd prime has a primitive root.

\begin{theorem}
Let $p$ be an odd prime.  Then any power of $p$ is a primitive root.
Moreover, if $r$ is a primitive root modulo $p^2$, then $r$ is a
primitive root modulo $p^m$ for all positive integers $m$.
\end{theorem}

\begin{proof}
By Theorem 62, we know that any prime $p$ has a primitive root $r$
which is also a primitive root modulo $p^2$, thus
\begin{equation}\label{1}
p^2\nmid (r^{p-1}-1).
\end{equation}
We will prove by induction that
\begin{equation}\label{2}
p^m\nmid (r^{p^{m-2}(p-1)}-1)
\end{equation}
for all integers $m\geq 2$. Once we prove the above congruence, we
show that $r$ is also a primitive root modulo $p^m$. Let
$n=ord_{p^m}r$.  By Theorem 54, we know that $n\mid \phi(p^m)$.
Also, we know that $\phi(p^m)=p^m(p-1)$.  Hence $n\mid p^m(p-1)$. On
the other hand, because
\begin{equation*}
p^m\mid (r^n- 1),
\end{equation*}
we also know that
\begin{equation*}
p\mid (r^n-1).
\end{equation*}
Since $\phi(p)=p-1$, we see that by Theorem 54, we have $n=l(p-1)$.
also $n\mid p^{m-1}(p-1)$, we have that $n=p^s(p-1)$, where $0 \leq
s\leq m-1$.  If $n=p^s(p-1)$ with $s\leq m-2$, then
\begin{equation*}
p^k\mid r^{p^{m-2}(p-1)}-1,
\end{equation*}
which is a contradiction.  Hence
\begin{equation*}
ord_{p^m}r=\phi(p^m).
\end{equation*}
\par We prove now (\ref{2}) by induction.  Assume that our
assertion is true for all $m\geq 2$.  Then
\begin{equation*}
p^m\nmid (r^{p^{m-2}(p-1)}-1).
\end{equation*}
Because $(r,p)=1$, we see that $(r,p^{m-1})=1$.  We also know from
Euler's theorem that
\begin{equation*}
p^{m-1}\mid (r^{p^{m-2}(p-1)}-1).
\end{equation*}
Thus there exists an integer $k$ such that
\begin{equation*}
r^{p^{m-2}(p-1)}=1+kp^{m-1}.
\end{equation*}
where $p\nmid k$ because $r^{p^{m-2}(p-1)}\not\equiv 1(mod \ p^m)$.
Thus we have now
\begin{eqnarray*}
r^{p^{m-1}(p-1)}&=&(1+kp^{m-1})^p\\ &\equiv&1+kp^m(mod \ p^{m+1})
\end{eqnarray*}
Because $p\nmid k$, we have
\begin{equation*}
p^{m+1}\nmid (r^{p^{m-1}(p-1)}-1).
\end{equation*}
\end{proof}

\begin{example}
Since 3 is a primitive root of 7, then 3 is a primitive root for
$7^k$ for all positive integers $k$.
\end{example}







\par In the following theorem, we prove that no power of 2, other
than 2 or 4, has a primitive root and that is because when $m$ is an
odd integer, $ord_2^km\neq \phi(2^k)$ and this is because $2^k\mid
(a^{\phi(2^k)/2}-1)$.

\begin{theorem}
If $m$ is an odd integer, and if $k\geq 3$ is an integer, then
\begin{equation*}
m^{2^{k-2}}\equiv 1(mod \ 2^k).
\end{equation*}
\end{theorem}

\begin{proof}
We prove the result by induction.  If $m$ is an odd integer, then
$m=2n+1$ for some integer $n$.  Hence,
\begin{equation*}
m^2=4n^2+4n+1=4n(n+1)+1.
\end{equation*}
It follows that $8\mid (m^2-1)$.\\
\par Assume now that
\begin{equation*}
2^k\mid (m^{2^{k-2}}-1).
\end{equation*}
Then there is an integer $q$ such that
\begin{equation*}
m^{2^{k-2}}=1+q.2^{k}.
\end{equation*}
Thus squaring both sides, we get
\begin{equation*}
m^{2^{k-1}}=1+q.2^{k+1}+q^22^{2k}.
\end{equation*}
Thus
\begin{equation*}
2^{k+1}\mid (m^{2^{k-1}}-1).
\end{equation*}
\end{proof}

Note now that 2 and 4 have primitive roots 1 and 3 respectively.
\par We now list the set of integers that do not have primitive
roots.

\begin{theorem}
If $m$ is not $p^a$ or  $2p^a$, then $m$ does not have a primitive
root.
\end{theorem}

\begin{proof}
Let $m=p_1^{s_1}p_2^{s_2}...p_i^{s_i}$. If $m$ has a primitive root
$r$ then $r$ and $m$ are relatively prime and $ord_mr=\phi(m)$. We
also have, we have $(r,p^s)=1$ where $p^s$ is of the primes in the
factorization of $m$.  By Euler's theorem, we have
\begin{equation*}
p^s\mid (r^{\phi(p^s)}-1).
\end{equation*}
Now let
\begin{equation*}
L=[\phi(p_1^{s_1}), \phi(p_2^{s_2}),...,\phi(p_i^{s_i})].
\end{equation*}
We know that
\begin{equation*}
r^L\equiv 1(mod \ p_k^{s_k})
\end{equation*}
for all $1\leq k\leq m$.  Thus using the Chinese Remainder Theorem,
we get
\begin{equation*}
m\mid (r^L-1),
\end{equation*}
which leads to $ord_mr=\phi(m)\leq L$. Now because
\begin{equation*}
\phi(m)=\phi(p_1^{s_1})\phi(p_2^{s_2})...\phi(p_n^{s_n})\leq
[\phi(p_1^{s_1}),\phi(p_2^{s_2}),...,\phi(p_n^{s_n})].
\end{equation*}
Now the inequality above holds only if
\begin{equation*}
\phi(p_1^{s_1}),\phi(p_2^{s_2}),...,\phi(p_n^{s_n})
\end{equation*}
are relatively prime.  Notice now that by Theorem 41,
\begin{equation*}
\phi(p_1^{s_1}),\phi(p_2^{s_2}),...,\phi(p_n^{s_n})
\end{equation*}
are not relatively prime unless $m=p^s$ or $m=2p^s$ where $p$ is an
odd prime and $t$ is any positive integer.
\end{proof}

We now show that all integers of the form $m=2p^s$ have primitive
roots.

\begin{theorem}
Consider a prime $p\neq 2$ and let $s$ is a positive integer, then
$2p^s$ has a primitive root.  In fact, if $r$ is an odd primitive
root modulo $p^s$, then it is also a primitive root modulo $2p^s$
but if $r$ is even, $r+p^s$ is a primitive root modulo $2p^s$.
\end{theorem}

\begin{proof}
If $r$ is a primitive root modulo $p^s$, then
\begin{equation*}
p^s\mid (r^{\phi(p^s)}-1)
\end{equation*}
and no positive exponent smaller than $\phi(p^s)$ has this property.
Note also that
\begin{equation*}
\phi(2p^s)=\phi(p^s),
\end{equation*}
so that
\begin{equation*}
p^s\mid (r^{\phi(2p^s)}-1).
\end{equation*}
\par If $r$ is odd, then
\begin{equation*}
2\mid (r^{\phi(2p^s)}-1).
\end{equation*}
Thus by Theorem 56, we get
\begin{equation*}
2p^s\mid (r^{\phi(2p^s)}-1).
\end{equation*}
It is important to note that no smaller power of $r$ is congruent to
1 modulo $2p^s$. This power as well would also be congruent to 1
modulo $p^s$ contradicting that $r$ is a primitive root of $p^s$. It
follows that $r$ is a primitive root modulo $2p^s$.
\par While, if $r$ is even, then $r+p^s$ is odd.
Hence
\begin{equation*}
2\mid ((r+p^s)^{\phi(2p^s)}-1).
\end{equation*}



Because $p^s\mid (r+p^s-r)$, we see that
\begin{equation*}
p^s\mid ((r+p^s)^{\phi(2p^s)}-1).
\end{equation*}
As a result, we see that $2p^s\mid ((r+p^s)^{\phi(2p^s)}-1)$ and
since for no smaller power of $r+p^s$ is congruent to 1 modulo
$2p^s$, we see that $r+p^s$ is a primitive root modulo $2p^s$.
\end{proof}

As a result, by Theorem 63, Theorem 65 and Theorem 66, we see that

\begin{theorem}
The positive integer $m$ has a primitive root if and only if $n=2,4,
p^s$ or $2p^s$
\end{theorem}

for prime $p\neq 2$ and $s$ is a positive integer. \\

\textbf{Exercises}
\begin{enumerate}
\item{Which of the following integers 4, 12, 28, 36, 125 have a
primitive root.}\item{Find a primitive root of 4, 25, 18.}\item{Find
all primitive roots modulo 22.}\item{Show that there are the same
number of primitive roots modulo $2p ^s$ as there are modulo $p^s$,
where $p$ is an odd prime and $s$ is a positive integer.}\item{Find
all primitive roots modulo 25.}\item{Show that the integer $n$ has a
primitive root if and only if the only solutions of the congruence
$x^2\equiv 1(mod n)$ are $x\equiv \pm1 (mod \ n)$.}
\end{enumerate}


\section{Introduction to Quadratic Residues and Nonresidues}
The question that we need to answer in this section is the
following.  If $p$ is an odd prime and $a$ is an integer relatively
prime to $p$. Is $a$ a perfect square modulo $p$. \index{Quadratic
Residue}
\begin{def1}
Let $m$ be a positive integer.  An integer $a$ is a quadratic
residue of $m$ if $(a,m)=1$ and the congruence $x^2\equiv a (mod \
m)$ is solvable. If the congruence $x^2\equiv a (mod \ m)$ has no
solution, then $a$ is a quadratic nonresidue of $m$.
\end{def1}
\index{Nonresidue}
\begin{example}
Notice that $1^2=6^2\equiv 1(mod \ 7)$, $3^2=4^2\equiv 2(mod \ 7)$
and $2^2=5^2\equiv 4(mod \ 7)$.  Thus $1,2,4$ are quadratic residues
modulo 7 while $3,5,6$ are quadratic nonresidues modulo 7.
\end{example}

\begin{lemma}
Let $p\neq 2$ be a prime number and $a$ is an integer such that
$p\nmid a$. Then either a is quadratic nonresidue modulo $p$ or
\begin{equation*}
x^2\equiv a(mod \ p)
\end{equation*}
has exactly two incongruent solutions modulo $p$.
\end{lemma}

\begin{proof}
If $x^2\equiv a(mod \ p)$ has a solution, say $x=x'$, then $-x'$ is
a solution as well.  Notice that $-x' \not\equiv x'(mod \ p)$
because then $p\mid 2x'$ and hence $p\nmid x_0$.
\par We now show that there are no more than two incongruent
solutions.  Assume that $x=x'$ and $x=x''$ are both solutions of
$x^2\equiv a(mod \ p)$.  Then we have
\begin{equation*}
(x')^2- (x'')^2=(x'+x'')(x'-x'')\equiv 0(mod \ p).
\end{equation*}
Hence
\begin{equation*}
x'\equiv x''(mod \ p)\ \ \mbox{or} \ \ x'\equiv -x''(mod \ p).
\end{equation*}
\end{proof}

The following theorem determines the number of integers that are
quadratic residues modulo an odd prime.

\begin{theorem}
If $p\neq 2$ is a prime, then there are exactly $(p-1)/2$ quadratic
residues modulo $p$ and $(p-1)/2$ quadratic nonresidues modulo $p$
in the set of integers $1,2...,p-1$.
\end{theorem}

\begin{proof}
To find all the quadratic residues of $p$ among all the integers
$1,2,...,p-1$, we determine the least positive residue modulo $p$ of
$1^2,2^2,...,(p-1)^2$. Considering the $p-1$ congruences and because
each congruence has either no solution or two incongruent solutions,
there must be exactly $(p-1)/2$ quadratic residues of $p$ among
$1,2,...,p-1$. Thus the remaining are $(p-1)/2$ quadratic
nonresidues of $p$.
\end{proof}

\textbf{Exercises}
\begin{enumerate}
\item{Find all the quadratic residues of 3.} \item{Find all the
quadratic residues of 13.} \item{find all the quadratic residues of
18.}\item{Show that if $p$ is prime and $p\geq 7$, then there are
always two consecutive quadratic residues of $p$.  Hint: Show that
at least one of $2,5$ or 10 is a quadratic residue of
$p$.}\item{Show that if $p$ is prime and $p\geq 7$, then there are
always two quadratic residues of $p$ that differ by 3.}
\end{enumerate}


\section{Legendre Symbol}
In this section, we define Legendre symbol which is a notation
associated to quadratic residues and prove related theorems.
\index{Legendre Symbol}
\begin{def1}
Let $p\neq 2$ be a prime and $a$ be an integer such that $p\nmid a$.
The Legendre symbol $\left(\frac{a}{p}\right)$ is defined by
\[\left(\frac{a}{p}\right)=\left\{\begin{array}{lcr}
\ 1  &\mbox{if a is a quadratic residue of p} \\
\ -1  &\mbox{if a is a quadratic nonresidue of p}. \\
\end{array}\right .\]
\end{def1}

\begin{example}
Notice that using the previous example, we see that
\begin{eqnarray*}
&&
\left(\frac{1}{7}\right)=\left(\frac{2}{7}\right)=\left(\frac{4}{7}\right)=1\\
&&
\left(\frac{3}{7}\right)=\left(\frac{5}{7}\right)=\left(\frac{6}{7}\right)=-1
\end{eqnarray*}
\end{example}
\index{Euler Criterion} In the following theorem, we present a way
to determine wether an integer is a quadratic residue of a prime.
\begin{theorem}\textbf{Euler's Criterion}\index{Euler's Criterion}
Let $p\neq 2$ be a prime and let $a$ be a positive integer such that
$p\nmid a$. Then
\begin{equation*}
\left(\frac{a}{p}\right)\equiv a^{\phi(p)/2}(mod \ p).
\end{equation*}
\end{theorem}

\begin{proof}
Assume that $\left(\frac{a}{p}\right)=1$.  Then the congruence
$x^2\equiv a(mod \ p)$ has a solution say $x=x'$.  According to
Fermat's theorem, we see that
\begin{equation*}
a^{\phi(p)/2}=((x')^2)^{\phi(p)/2}\equiv 1(mod\ p).
\end{equation*}
Now if $\left(\frac{a}{p}\right)=-1$, then $x^2\equiv a(mod \ p)$ is
not solvable. Thus by Theorem 26, we have that for each integer k
with $(k,p)=1$ there is an integer $l$ such that $kl\equiv a(mod \
p)$. Notice that $i\neq j$ since $x^2\equiv a(mod \ p)$ has no
solutions. Thus we can couple the integers $1,2,...,p-1$ into
$(p-1)/2$ pairs, each has product $a$. Multiplying these pairs
together, we find out that
\begin{equation*}
(p-1)!\equiv a^{\phi(p)/2}(mod \ p).
\end{equation*}
Using Wilson's Theorem, we get
\begin{equation*}
\left(\frac{a}{p}\right)=-1\equiv a^{(p-1)/2}(mod \ p).
\end{equation*}
\end{proof}

\begin{example}
Let $p=13$ and $a=3$.  Then $\left(\frac{3}{13}\right)=-1\equiv
3^{6}(mod \ 13).$
\end{example}

We now prove some properties of Legendre symbol.

\begin{theorem}
Let $p\neq 2$ be a prime. Let $a$ and $b$ be integers such that
$p\nmid a$, $p\nmid b$ and $p\mid (a-b)$ then
\begin{equation*}
\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right).
\end{equation*}
\end{theorem}

\begin{proof}
Since $p\mid (a-b)$, then $x^2\equiv a(mod \ p)$ has a solution if
and only if $x^2\equiv b(mod \ p)$ has a solution. Hence
\begin{equation*}
\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)
\end{equation*}
\end{proof}

\begin{theorem}
Let $p\neq 2$ be a prime. Let $a$ and $b$ be integers such that
$p\nmid a$, $p\nmid b$ then
\begin{equation*}
\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right)
\end{equation*}
\end{theorem}

By Euler's criterion, we have
\begin{equation*}
\left(\frac{a}{p}\right)\equiv a^{\phi(p)/2}(mod \ p)
\end{equation*}
and
\begin{equation*}
\left(\frac{b}{p}\right)\equiv b^{\phi(p)/2}(mod \ p).
\end{equation*}
Thus we get
\begin{equation*}
\left(\frac{a}{p}\right)\left(\frac{b}{p}\right) \equiv
(ab)^{\phi(p)/2}\equiv \left(\frac{ab}{p}\right)(mod \ p).
\end{equation*}
We now show when is $-1$ a quadratic residue of a prime $p$ .

\begin{cor}
If $p\neq 2$ is a, then
\[\left(\frac{-1}{p}\right)=\left\{\begin{array}{lcr}
\ 1  &{\mbox{if}\  p\equiv 1(mod \ 4)} \\
\ -1  &{\mbox{if}\  p\equiv -1(mod \ 4)}. \\
\end{array}\right .\]
\end{cor}

\begin{proof}
By Euler's criterion, we know that
\begin{equation*}
\left(\frac{a}{p}\right)=(-1)^{\phi(p)/2}(mod \ p)
\end{equation*}
If $4\mid (p-1)$, then $p=4m+1$ for some integer $m$ and thus we get
\begin{equation*}
(-1)^{\phi(p)/2}=(-1)^{2m}=1.
\end{equation*}
and if $4\mid (p-3)$, then $p=4m+3$ for some integer $m$ and we also
get
\begin{equation*}
(-1)^{\phi(p)/2}=(-1)^{2m+1}=-1.
\end{equation*}
\end{proof}

We now determine when $2$ is a quadratic residue of a prime $p$.

\begin{theorem}
For every odd prime $p$ we have
\[\left(\frac{2}{p}\right)=\left\{\begin{array}{lcr}
\ 1  &{\mbox{if}\  p\equiv \pm1(mod \ 8)} \\
\ -1  &{\mbox{if}\  p\equiv \pm 3(mod \ 8)}. \\
\end{array}\right .\]
\end{theorem}

\begin{proof}
Consider the following $(p-1)/2$ congruences
\begin{eqnarray*}
p-1&\equiv& 1(-1)^1 \ \ \ (mod \ p)\\
2&\equiv& 2(-1)^2 \ \ \ (mod \ p)\\
p-3&\equiv& 3(-1)^3 \ \ \  (mod \ p)\\
4&\equiv& 4(-1)^4 \ \ \ (mod \ p)\\
&.& \\
&.& \\
&.& \\
r&\equiv& \frac{p-1}{2}(-1)^{(p-1)/2} \ \ \ (mod \ p),\\
\end{eqnarray*}
where $r$ is either $p-(p-1)/2$ or $(p-1)/2$.  Multiplying all these
equations we get,
\begin{equation*}
2.4.6...(p-1)\equiv
\left(\frac{p-1}{2}\right)!(-1)^{1+2+...+(p-1)/2} \ \ \ (mod \ p).
\end{equation*}
This gives us
\begin{equation*}
2^{(p-1)/2}\left(\frac{p-1}{2}\right)! \equiv
\left(\frac{p-1}{2}\right)!(-1)^{(p^2-1)/8} (mod \ p).
\end{equation*}
Now notice that $\left(\frac{p-1}{2}\right)!\not\equiv 0(mod \ p)$
and thus we get
\begin{equation*}
2^{(p-1)/2}\equiv (-1)^{(p^2-1)/8}(mod \ p).
\end{equation*}
Note also that by Euler's criterion, we get
\begin{equation*}
2^{\phi(p)/2}\equiv \left(\frac{2}{p}\right)(mod \ p),
\end{equation*}
and since each member is 1 or -1 the two members are equal.
\end{proof}

We now present an important lemma that determines whether an integer
is a quadratic residue of a prime or not. \index{Gauss's Lemma}
\begin{lemma}\textbf{Gauss's Lemma} Let $p\neq 2$ be a prime and
$a$ a relatively prime integer to $p$.  If $k$ counts the number of
least positive residues of the integers $a, 2a,...,((p-1)/2)a$ that
are greater than $p/2$, then
\begin{equation*}
\left(\frac{a}{p}\right)=(-1)^k.
\end{equation*}
\end{lemma}

\begin{proof}
Let $m_1,m_2,...,m_s$ be those integers greater than $p/2$ in the
set of the least positive residues of the integers $a,
2a,...,((p-1)/2)a$ and let $n_1,n_2,...,n_t$ be those less than
$p/2$. We now show that
\begin{equation*}
p-m_1,p-m_2,...,p-m_k,p-n_1,p-n_2,...,p-n_t
\end{equation*}
are precisely the integers
\begin{equation*}
1,2,...,(p-1)/2,
\end{equation*}
in the same order.
\par So we shall show that no two integers of these are
congruent modulo $p$, because there are exactly $(p-1)/2$ numbers in
the set, and all are positive integers less than or equal to
$(p-1)/2$. Notice that $m_i\not\equiv m_j (\mod \ p)$ for all $i\neq
j$ and $n_i\not\equiv n_j (\mod \ p)$ for all $i\neq j$.  If any of
these congruences fail, then we will have that $r\equiv s(mod \ p)$
assuming that $ra\equiv sa(mod \ p)$. Also any of the integers
$p-m_i$ can be congruent to any of the $n_i$'s. Because if such
congruence holds, then we have $ra\equiv p-sa(mod \ p)$, so that
$ra\equiv -sa(mod \ p)$.  Because $p\nmid a$, this implies that
$r\equiv -s(mod \ p)$, which is impossible. We conclude that
\begin{equation*}
\prod_{i=1}^k(p-m_i)\prod_{i=1}^tn_i\equiv
\left(\frac{p-1}{2}\right)!(mod \ p),
\end{equation*}
which implies
\begin{equation*}
(-1)^sm_1m_2...(p-m_k)n_1n_2...n_t\equiv
\left(\frac{p-1}{2}\right)!(mod \ p),
\end{equation*}
Simplifying, we get
\begin{equation*}
m_1m_2...(p-m_k)n_1n_2...n_t\equiv a.2a...((p-1)/2)=
a^{(p-1)/2}((p-1)/2)!( mod \ p).
\end{equation*}
As a result, we have that
\begin{equation*}
a^{(p-1)/2}((p-1)/2)!\equiv ((p-1)/2)!(mod \ p)
\end{equation*}
Note that since $(p,((p-1)/2)!)=1$, we get
\begin{equation*}
(-1)^ka^{(p-1)/2}\equiv 1(mod \ p).
\end{equation*}
Thus we get
\begin{equation*}
a^{(p-1)/2}\equiv(-1)^k(mod \ p).
\end{equation*}
Using Euler's criterion, the result follows.
\end{proof}

\begin{example}
To find $\left(\frac{5}{13}\right)$ using Gauss's lemma, we
calculate
\begin{equation*}
\sum_{i=1}^6[5i/13]=[5/13]+[10/13]+[15/13]+[20/13]+[25/13]+[30/13]=5
\end{equation*}
Thus we get $\left(\frac{5}{13}\right)=(-1)^5=-1$.
\end{example}

\textbf{Exercises}
\begin{enumerate}
\item{Find all quadratic residues of 3}\item{Find all quadratic
residues of 19.}\item{Find the value of Legendre symbol
$\left(\frac{j}{7}\right)$ for $j=1,2,3,4,5,6$.}\item{Evaluate the
Legendre symbol $\left(\frac{7}{11}\right)$by using Euler's
criterion.}\item{Let $a$ and $b$ be integers not divisible by $p$.
 Show that either one or all three of the integers $a,b$ and $ab$ are quadratic residues of $p$.}
\item{Let $p$ be a prime and $a$ be a quadratic residue of $p$.
Show that if $p\equiv 1(mod \ 4)$, then $-a$ is also a quadratic
residue of $p$, whereas if $p\equiv 3(mod \ 4)$, then $-a$ is a
quadratic nonresidue of $p$.}
 \item{Show that if $p$ is an odd prime and a is an integer not
divisible by $p$ then $\left(\frac{a^2}{p}\right)=1$.}
\end{enumerate}

\section{The Law of Quadratic Reciprocity}
Given that $p$ and $q$ are odd primes.  Suppose we know whether $q$
is a quadratic residue of $p$ or not.  The question that this
section will answer is whether $p$ will be a quadratic residue of
$q$ or not. Before we state the law of quadratic reciprocity, we
will present a Lemma of Eisenstein which will be used in the proof
of the law of reciprocity.  The following lemma will relate Legendre
symbol to the counting lattice points in the triangle.

\begin{lemma}
If $p\neq 2$ is a prime and $a$ is an odd integer such that $p\nmid
a$, then
\begin{equation*}
\left(\frac{a}{p}\right)=(-1)^{\sum_{i=1}^{(p-1)/2}[ia/p]}.
\end{equation*}

\begin{proof}
Consider the least positive residues of the integers $a,
2a,...,((p-1)/2)a$; let $m_1,m_2,...,m_s$ be integers of this set
such that $m_i>p/2$ for all $i$ and let $n_1,n_2,...,n_t$ be those
integers where $n_i<p/2$. Using the division algorithm, we see that
\begin{equation*}
ia=p[ia/p]+r
\end{equation*}
where $r$ is one of the $m_i$ or $n_i$.  By adding the $(p-1)/2$
equations, we obtain
\begin{equation}\label{qr1}
\sum_{i=1}^{(p-1)/2}ia=\sum_{i=1}^{(p-1)/2}p[ia/p]+\sum_{i=1}^sm_i+\sum_{i=1}^tn_i.
\end{equation}
As in the proof of Gauss's Lemma, we see that
\begin{equation*}
p-m_1,p-m_2,...,p-m_s,p-n_1,p-n_2,...,p-n_t
\end{equation*}
are precisely the integers $1,2,...,(p-1)/2$, in the same order. Now
we obtain
\begin{equation}\label{qr2}
\sum_{i=1}^{(p-1)/2}i=\sum_{i=1}^s(p-m_i)+\sum_{i=1}^tn_i=ps-\sum_{i=1}^sm_i+\sum_{i=1}^tn_i.
\end{equation}
We subtract $(\ref{qr2})$ from $(\ref{qr1})$ to get
\begin{equation*}
\sum_{i=1}^{(p-1)/2}ia-\sum_{i=1}^{(p-1)/2}i=\sum_{i=1}^{(p-1)/2}p[ia/p]-ps+2\sum_{i=1}^sm_i.
\end{equation*}
Now since we are taking the following as exponents for $-1$, it
suffice to look at them modulo 2.  Thus
\begin{equation*}
0\equiv \sum_{i=1}^{(p-1)/2}[ia/p]-s(mod \ 2).
\end{equation*}
\begin{equation*}
\sum_{i=1}^{(p-1)/2}[ia/p]\equiv s(mod \ 2)
\end{equation*}
Using Gauss's lemma, we get
\begin{equation*}
\left(\frac{a}{p}\right)=(-1)^s=(-1)^{\sum_{i=1}^{(p-1)/2}[ia/p]}.
\end{equation*}
\end{proof}
\end{lemma}
\index{Quadratic Reciprocity}
\begin{theorem}\textbf{The Law of Quadratic Reciprocity}
Let $p$ and $q$ be distinct odd primes.  Then
\begin{equation*}
\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}.\frac{q-1}{2}}
\end{equation*}
\end{theorem}

\begin{proof}
We consider now the pairs of integers also known as lattice points
$(x,y)$ with
\begin{equation*}
1\leq x\leq (p-1)/2 \mbox{and} \ \  1\leq y\leq (q-1)/2.
\end{equation*}
The number of such pairs is $\frac{p-1}{2}.\frac{q-1}{2}$. We divide
these pairs into two groups depending on the sizes of $qx$ and $py$.
Note that $qx\neq py$ for all pairs because $p$ and $q$ are distinct
primes.
\par We now count the pairs of integers $(x,y)$ with
\begin{equation*}
1\leq x\leq (p-1)/2, \ \ 1\leq y\leq (q-1)/2 \mbox{and} \ \ qx>py.
\end{equation*}
Note that these pairs are precisely those where
\begin{equation*}
1\leq x\leq (p-1)/2 \mbox{and} \ \ 1\leq y\leq qx/p.
\end{equation*}
For each fixed value of $x$ with $1\leq x\leq (p-1)/2$, there are
$[qx/p]$ integers satisfying $1\leq y\leq qx/p$. Consequently, the
total number of pairs with are
\begin{equation*}
1\leq x\leq (p-1)/2, \ \ 1\leq y\leq qx/p, \mbox{and} \ \ qx>py
\end{equation*}
is
\begin{equation*}
\sum_{i=1}^{(p-1)/2}[qi/p].
\end{equation*}
\par Consider now the pair of integers $(x,y)$ with
\begin{equation*}
1\leq x\leq (p-1)/2, \ \ 1\leq y\leq (q-1)/2, \mbox{and} \ \  qx<py.
\end{equation*}
Similarly, we find that the total number of such pairs of integers
is
\begin{equation*}
\sum_{i=1}^{(q-1)/2}[pi/q].
\end{equation*}
Adding the numbers of pairs in these classes, we see that
\begin{equation*}
\sum_{i=1}^{(p-1)/2}[qi/p]+
\sum_{i=1}^{(q-1)/2}[pi/q]=\frac{p-1}{2}.\frac{q-1}{2},
\end{equation*}
and hence using Lemma 14, we get that
\begin{equation*}
\left(\frac{p}{q}\right)\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}.\frac{q-1}{2}}
\end{equation*}
\end{proof}

\textbf{Exercises}
\begin{enumerate}
\item{Evaluate $\left(\frac{3}{53}\right)$.}\item{Evaluate
$\left(\frac{31}{641}\right)$.}\item{Using the law of quadratic
reciprocity, show that if $p$ is an odd prime, then
\[\left(\frac{3}{p}\right)=\left\{\begin{array}{lcr}
\ 1  &{\mbox{if}\  p\equiv \pm1(mod \ 12)} \\
\ -1  &{\mbox{if}\  p\equiv \pm 5(mod \ 12)}. \\
\end{array}\right .\]}\item{Show that if $p$ is an odd prime, then
\[\left(\frac{-3}{p}\right)=\left\{\begin{array}{lcr}
\ 1  &{\mbox{if}\  p\equiv 1(mod \ 6)} \\
\ -1  &{\mbox{if}\  p\equiv -1 (mod \ 6)}. \\
\end{array}\right .\]}\item{Find a congruence describing all primes for which 5 is a quadratic residue.}
\end{enumerate}

\section{Jacobi Symbol}
In this section, we define the Jacobi symbol which is a
generalization of the Legendre symbol.  The Legendre symbol was
defined in terms of primes, while Jacobi symbol will be generalized
for any odd integers and it will be given in terms of Legendre
symbol. \index{Jacobi Symbol}
\begin{definition}
Let $n$ be an odd positive integer with prime factorization
$n=p_1^{a_1}p_2^{a_2}...p_m^{a_m}$ and let $a$ be an integer
relatively prime to $n$, then
\begin{equation*}
\left(\frac{a}{n}\right)=\prod_{i=1}^m\left(\frac{a}{p_i}\right)^{c_i}.
\end{equation*}
\end{definition}

\begin{example}
Notice that from the prime factorization of 45, we get that
\begin{equation*}
\left(\frac{2}{55}\right)=\left(\frac{2}{5}\right)\left(\frac{2}{11}\right)=(-1)(-1)=1
\end{equation*}
\end{example}

We now prove some properties for Jacobi symbol that are similar to
the properties of Legendre symbol.

\begin{theorem}
Let $n$ be an odd positive integer and let $a$ and $b$ be integers
such that$(a,n)=1$ and $(b,n)=1$.  Then
\begin{enumerate}
\item{if $n \mid (a-b)$, then
\begin{equation*}
\left(\frac{a}{n}\right)=\left(\frac{b}{n}\right).\end{equation*}}
\item{\begin{equation*}\left(\frac{ab}{n}\right)=\left(\frac{a}{n}\right)\left(\frac{b}{n}\right).\end{equation*}}
\end{enumerate}
\end{theorem}
\begin{proof}
\textbf{Proof of 1:} Note that if $p$ is in the prime factorization
of $n$, then we have that $p\mid (a-b)$.  Hence by Theorem 70, we
get that
\begin{equation*}
\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right).
\end{equation*}
As a result, we have
\begin{equation*}
\left(\frac{a}{n}\right)=\prod_{i=1}^m\left(\frac{a}{p_i}\right)^{c_i}=
\prod_{i=1}^{m}\left(\frac{b}{p_i}\right)^{c_i}
\end{equation*}
\textbf{Proof of 2:} Note that by Theorem 71, we have
$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$
for any prime $p$ appearing in the prime factorization of $n$.  As a
result, we have
\begin{eqnarray*}
\left(\frac{ab}{n}\right)&=&\prod_{i=1}^m\left(\frac{ab}{p_i}\right)^{c_i}\\
&=&\prod_{i=1}^m\left(\frac{a}{p_i}\right)^{c_i}\prod_{i=1}^m\left(\frac{b}{p_i}\right)^{c_i}
\\&=&\left(\frac{a}{n}\right)\left(\frac{b}{n}\right).
\end{eqnarray*}
\end{proof}

In the following theorem, we determine $\left(\frac{-1}{n}\right)$
and $\left(\frac{2}{n}\right)$.
\begin{theorem}
Let $n$ be an odd positive integer.  Then
\begin{enumerate}
\item{\begin{equation*}\left(\frac{-1}{n}\right)=(-1)^{(n-1)/2}.\end{equation*}}
\item{\begin{equation*}\left(\frac{2}{n}\right)=(-1)^{(n^2-1)/8}.\end{equation*}}
\end{enumerate}
\end{theorem}
\begin{proof}
\textbf{Proof of 1:}  If $p$ is in the prime factorization of $n$,
then by Corollary 3, we see that
$\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}$.  Thus
\begin{eqnarray*}
\left(\frac{-1}{n}\right)&=&\prod_{i=1}^m\left(\frac{-1}{p_i}\right)^{c_i}\\
\\ &=& (-1)^{\sum_{i=1}^mc_i(p_i-1)/2}.
\end{eqnarray*}
Notice that since $p_i-1$ is even, we have
\begin{equation*}
p_i^{a_i}=(1+(p_i-1))^{c_i}\equiv 1+c_i(p_i-1)(mod \ 4)
\end{equation*}
and hence we get
\begin{equation*}
n=\prod_{i=1}^mp_i^{c_i}\equiv 1+\sum_{i=1}^mc_i(p_i-1)(mod \ 4).
\end{equation*}
As a result, we have
\begin{equation*}
(n-1)/2\equiv \sum_{i=1}^mc_i(p_i-1)/2 \ (mod \ 2).
\end{equation*}
\textbf{Proof of 2:}  If $p$ is a prime, then by Theorem 72 we have
\begin{equation*}
\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}.
\end{equation*}
Hence
\begin{equation*}
\left(\frac{2}{n}\right)=(-1)^{\sum_{i=1}^mc_i(p_i^2-1)/8}.
\end{equation*}
Because $8 \mid p_i^2-1$, we see similarly that
\begin{equation*}
(1+(p_i^2-1))^{c_i}\equiv 1+c_i(p_i^2-1)(mod \ 64)
\end{equation*}
and thus
\begin{equation*}
n^2\equiv 1+\sum_{i=1}^mc_i(p_i^2-1) (mod \ 64),
\end{equation*}
which implies that
\begin{equation*}
(n^2-1)/8\equiv \sum_{i=1}^mc_i(p_i^2-1)/8 (mod \ 8).
\end{equation*}
\end{proof}

We now show that the reciprocity law holds for Jacobi symbol.

\begin{theorem}  Let $(a,b)=1$ be odd positive
integers.  Then
\begin{equation*}
\left(\frac{b}{a}\right)\left(\frac{a}{b}\right)=(-1)^{\frac{a-1}{2}.\frac{b-1}{2}}.
\end{equation*}
\end{theorem}

\begin{proof}
Notice that since $a=\prod_{j=1}^mp_i^{c_i}$ and
$b=\prod_{i=1}^nq_i^{d_i}$ we get
\begin{equation*}
\left(\frac{b}{a}\right)\left(\frac{a}{b}\right)=
\prod_{i=1}^n\prod_{j=1}^m\left[\left(\frac{p_j}{q_i}\right)\left(\frac{q_i}{p_j}\right)\right]^{c_jd_i}
\end{equation*}
By the law of quadratic reciprocity, we get
\begin{equation*}
\left(\frac{b}{a}\right)\left(\frac{a}{b}\right)=
(-1)^{\sum_{i=1}^n\sum_{j=1}^mc_j\left(\frac{p_j-1}{2}\right)d_i\left(\frac{q_i-1}{2}\right)}
\end{equation*}
As in the proof of part 1 of Theorem 75, we see that
\begin{equation*}
\sum_{j=1}^mc_j\left(\frac{p_j-1}{2}\right)\equiv \frac{a-1}{2}(mod
\ 2)
\end{equation*}
and
\begin{equation*}
\sum_{i=1}^nd_i\left(\frac{q_i-1}{2}\right)\equiv \frac{b-1}{2}(mod
\ 2).
\end{equation*}
Thus we conclude that
\begin{equation*}
\sum_{j=1}^mc_j\left(\frac{p_j-1}{2}\right)\sum_{i=1}^nd_i\left(\frac{q_i-1}{2}\right)\equiv
\frac{a-1}{2}.\frac{b-1}{2}(mod \ 2).
\end{equation*}
\end{proof}

\textbf{Exercises}
\begin{enumerate}
\item{Evaluate $\left(\frac{258}{4520}\right)$.}\item{Evaluate
$\left(\frac{1008}{2307}\right)$.}\item{For which positive integers
$n$ that are relatively prime to 15 does the Jacobi symbol
$\left(\frac{15}{n}\right)$ equal 1?}\item{Let $n$ be an odd square
free positive integer.  Show that there is an integer $a$ such that
$(a,n)=1$ and $\left(\frac{a}{n}\right)=-1$.}
\end{enumerate}







\chapter{Introduction to Continued Fractions}
In this chapter, we introduce continued fractions, prove their basic
properties and apply these properties to solve some problems. Being
a very natural object, continued fractions appear in many areas of
Mathematics, sometimes in an unexpected way. The Dutch mathematician
and astronomer, Christian Huygens (1629-1695), made the first
practical application of the theory of "anthyphaeiretic ratios" (the
old name of continued fractions) in 1687. He wrote a paper
explaining how to use convergents to find the best rational
approximations for gear ratios. These approximations enabled him to
pick the gears with the best numbers of teeth. His work was
motivated by his desire to build a mechanical planetarium. Further
continued fractions attracted attention of most prominent
mathematicians. Euler, Jacobi, Cauchy, Gauss and many others worked
with the subject. Continued fractions find their applications in
some areas of contemporary Mathematics. There are mathematicians who
continue to develop the theory of continued fractions nowadays, The
Australian mathematician A.J. van der Poorten is, probably, the most
prominent among them.




\section{Basic Notations}
In general, \index{Simple Continued Fraction} a (simple) continued
fraction is an expression of the form
$$
a_0 + \frac{1}{a_1+\frac{\displaystyle 1}{\displaystyle a_2+
\ldots}},
$$
where the letters $a_0$, $\ a_1$, $\ a_2$, $\ldots$ denote
independent variables, and may be interpreted as one wants (e.g.
real or complex numbers, functions, etc.). This expression has
precise sense if the number of terms is finite, and may have no
meaning for an infinite number of terms. In this section we only
discuss the simplest classical setting.

\begin{center}{\it The letters $\ a_1$, $\ a_2$, $\ldots$ denote positive integers. The letter
$a_0$ denotes an integer.}
\end{center}

The following standard notation is very convenient.

\begin{notation}
We write
$$
[a_0; a_1,a_2, \ldots, a_n] = a_0 + \frac{1}{a_1+\frac{\displaystyle
1} {\displaystyle a_2+ \ldots
\genfrac{}{}{0cm}{0}{}{+\frac{\displaystyle 1}{\displaystyle a_n}}
}}
$$
if the number of terms is finite, and
$$
[a_0; a_1,a_2, \ldots] = a_0 + \frac{1}{a_1+\frac{\displaystyle
1}{\displaystyle a_2+ \ldots}}
$$
for an infinite number of terms.
\end{notation}

Still, in the case of infinite number of terms a certain amount of
work must be carried out in order to make the above formula
meaningful. At the same time, for the finite number of terms the
formula makes sense.

\begin{example}
$$
[-2;1,3,5] = -2 + 1/(1+1/(3+1/5)) = -2+1/(1+5/16) = -2+1/(21/16) =
-2+16/21 = -26/21
$$
\end{example}
\index{Continued Fractions}
\begin{notation}
For a finite continued fraction $ [a_0;a_1,a_2, \ldots, a_n] $ and a
positive integer $k \leq n$, the $k$-th remainder is defined as the
continued fraction
$$
r_k=[a_k;a_{k+1}, a_{k+2}, \ldots, a_n].
$$

Similarly, for an infinite  continued fraction $ [a_0;a_1,a_2,
\ldots] $ and a positive integer $k$,  the $k$-th remainder is
defined as the continued fraction
$$
r_k=[a_k;a_{k+1}, a_{k+2}, \ldots].
$$
\end{notation}

Thus, at least in the case of a finite continued fraction,
$$
\alpha=[a_0;a_1,a_2,\ldots, a_n] =a_0+1/(a_1+1/(a_2+ \ldots +1/a_n))
$$
we have
\begin{equation} \label{remainder}
\alpha =  a_0+1/(a_1+1/(a_2+ \ldots +1/(a_{k-1}+1/r_k)    )) =
"[a_0;a_1,a_2,\ldots, a_{k-1},r_k]"
\end{equation}
for any positive $k\leq n$. Quotation signs appear because we
consider the expressions of this kind only with integer entries but
the quantity $r_k$ may be a non-integer.

It is not difficult to expand any rational number $\alpha$ into a
continued fraction. Indeed, let $a_0=[\alpha]$ be the greatest
integer not exceeding $\alpha$. Thus the difference $\delta=\alpha -
a_0 <1$ and, of course, $\delta \geq 0$. If $\delta = 0$ then we are
done. Otherwise put $r_1 = 1/\delta$, find $a_1=[r_1]$ and
non-negative $\delta=\alpha_1 - a_1 <1$. Continue the procedure
until you obtain $\delta = 0$.

\begin{example}
Consider the continued fraction expansion for $42/31$. We obtain
$a_0=[42/31]=1$, $\delta = 42/31-1=11/31$.  Now $r_1=
1/\delta=31/11$ and $a_1=[\alpha_1]=[31/11]=2$. The new $\delta =
31/11-2=9/11$.  Now $r_2= 1/\delta=11/9$ and
$a_2=[\alpha_2]=[11/9]=1$. It follows that $\delta = 11/9-1 = 2/9$.
Now $r_3= 1/\delta=9/2$ and $a_3=[\alpha_3]=[9/2]=4$. It follows
that $\delta =9/2-4=1/2$. Now $r_4= 1/\delta=2$ and
$a_4=[\alpha_4]=[2]=2$. It follows that $\delta = 2-2=0$ and we are
done.
\par
Thus we have calculated
$$
42/31=[a_0;a_1,a_2,a_3,a_4] = [1;2,1,4,2].
$$
\end{example}

The above example shows that the algorithm stops after finitely many
steps. This is in fact quite a general phenomenon. In order to
practice with the introduced notations let us prove a simple but
important proposition. \index{Rational Number}
\begin{prop} \label{ratrep}
Any rational number can be represented as a finite continued
fraction.

\end{prop}
\par
{\sl Proof.} By construction, all remainders are positive rationals.
For a positive integer $k$ put $r_k=A/B$ and let $a_k=[r_k]$. Then
\begin{equation} \label{l2}
r_k-a_k = \frac{A-Ba_k}{B} := \frac{C}{B}.
\end{equation}
with $C<B$ because $r_k - a_k <1$ by construction. If $C=0$, then
the algorithm stops at this point and we are done. Assume now that
$C \neq 0$. It follows from (\ref{remainder}) that
\begin{equation} \label{l1}
r_k=a_k+\frac{1}{r_{k+1}}.
\end{equation}
Compare now (\ref{l2}) with (\ref{l1}) to find that
$$
r_{k+1} = \frac{B}{C}.
$$
Since $C<B$, the rational number $r_{k+1}$ has a denominator which
is smaller than the the denominator of the previous remainder $r_k$.
It follows that after a finite number of steps we obtain an integer
(a rational with $1$ in the denominator) $r_n=a_n$ and the procedure
stops at this point.

There appear several natural questions in the connection with
Proposition \ref{ratrep}.

Is such a continued fraction representation unique? The immediate
answer is "no". Here are two "different" continued fraction
representations for $1/2$:
$$
\frac{1}{2}=[0;2]=[0;1,1].
$$
However, we require that $a_n>1$, where $a_n$  is the last element
of a finite continued fraction. Then the answer is "yes".


{\sl Hint.} Make use of the formulas (\ref{main}) below.

From now on we assume that $a_n>1$.

Another natural question is about infinite continued fractions and
(as one can easily guess) real numbers. The proof of the
corresponding result is slightly more involved, and we do not give
it here. In this brief introduction we just formulate the result and
refer to the literature (\cite[Theorem 14]{Khinchin}) for a complete
proof. We, however, provide some remarks concerning this result
below. In particular, we will explain at some point, what the
convergence means.

\begin{theorem} \label{realrep}
An infinite continued fraction converges and defines a real number.
There is a one-to-one correspondence between

$\bullet$ all (finite and infinite) continued fractions
$[a_0;a_1,a_2, \ldots]$ with an integer $a_0$ and positive integers
$a_k$ for $k>0$ (and the last term $a_n>1$ in the case of finite
continued fractions)

and

$\bullet$ real numbers.

\end{theorem}

Note that the algorithm we developed above can be applied to any
real number and provides the corresponding continued fraction.

Theorem \ref{realrep} has certain theoretical significance.
L.Kronecker  (1823-1891) said, "God created the integers;  the rest
is  work of man". Several ways to represent real numbers out of
integers are well-known. Theorem \ref{realrep} provides yet another
way to fulfill this task. This way is constructive and at the same
time is not tied to any particular base (say to decimal or binary
decomposition).

We will discuss some examples later. \\
\textbf{Exercises}
\begin{enumerate}
\item{Prove that under the assumption $a_n>1$ the continued
fraction representation given in Proposition \ref{ratrep} is unique.
In other words, the correspondence between

$\bullet$ finite continued fractions $[a_0;a_1,a_2, \ldots a_n]$
with an integer $a_0$, positive integers $a_k$ for $k>0$ and $a_n>1$

and

$\bullet$ rational numbers

is one-to-one.}
\end{enumerate}

\section{Main Technical Tool}

Truncate finite (or infinite) continued fraction
$\alpha=[a_0;a_1,a_2, \ldots, a_n]$ at the $k$-th place (with $k<n$
in the finite case). The rational number $s_k=[a_0;a_1,a_2, \ldots,
a_k]$ is called the $k$-th {\sl convergent} of $\alpha$. Define the
integers $p_k$ and $q_k$ by
\begin{equation} \label{d2}
s_k = \frac{p_k}{q_k}
\end{equation}
written in the reduced form with $q_k>0$.

The following recursive transformation law takes place.
\begin{theorem} \label{MAIN}
For $k \geq 2$
\begin{equation} \label{main}
\begin{array}{c}
\displaystyle
p_k=a_kp_{k-1} + p_{k-2} \\
\displaystyle q_k=a_kq_{k-1} + q_{k-2}.
\end{array}
\end{equation}

\end{theorem}
{\sl Remark.} It does not matter here whether we deal with finite or
infinite continued fractions: the convergents are finite anyway.
\index{Convergents} {\sl Proof.} We use the induction argument on
$k$. For $k=2$ the statement is true.



Now, assume (\ref{main}) for $2 \leq k < l$. Let
$$
\alpha=[a_0;a_1,a_2,\ldots a_l]=\frac{p_l}{q_l}
$$
be an arbitrary continued fraction of length $l+1$. We denote by
$p_r/q_r$ the $r$-th convergent $\alpha$. Consider also the
continued fraction
$$
\beta = [a_1;a_2, \ldots, a_l]
$$
and denote by $p'_r/q'_r$ its $r$-th convergent. We have
$\alpha=a_0+1/\beta$ which translates as
\begin{equation} \label{l3}
\begin{array}{l}
p_l=a_0p'_{l-1} + q'_{l-1} \\
q_l=p'_{l-1}.
\end{array}
\end{equation}
Also, by the induction assumption,
\begin{equation} \label{l4}
\begin{array}{l}
p'_{l-1}=a_lp'_{l-2} + p'_{l-3} \\
q'_{l-1}=a_lq'_{l-2} + q'_{l-3}
\end{array}
\end{equation}
Combining (\ref{l3}) and (\ref{l4}) we obtain the formulas
$$
p_l=a_0(a_lp'_{l-2} + p'_{l-3}) + a_lq'_{l-2} + q'_{l-3} =
a_l(a_0p'_{l-2} + q'_{l-2}) + (a_0p'_{l-3} + q'_{l-3}) = a_lp_{l-1}
+ p_{l-2}
$$
and
$$
q_l=a_lp'_{l-2} +p'_{l-3}=a_lq_{l-1}+ q_{l-2},
$$
which complete the induction step. We have thus proved that
$$
s_k = \frac{p_k}{q_k},
$$
where $p_k$ and $q_k$ are defined by the recursive formulas
(\ref{main}). We still have to check that these are the quantities
defined by (\ref{d2}), namely that $q_k>0$ and that $q_k$ and $p_k$
are relatively prime. The former assertion follows from (\ref{main})
since $a_k>0$ for $k>0$. To prove the latter assertion, multiply the
equations (\ref{main}) by $q_{k-1}$ and $p_{k-1}$ respectively and
subtract them. We obtain
\begin{equation} \label{l5}
p_kq_{k-1} - q_kp_{k-1} = -(p_{k-1}q_{k-2} - q_{k-1} p_{k-2}).
\end{equation}

This concludes the proof of Theorem \ref{main}. As an immediate
consequence of (\ref{main}) we find that

\begin{equation} \label{dif1}
\frac{p_{k-1}}{q_{k-1}} - \frac{p_k}{q_k} =
\frac{(-1)^k}{q_kq_{k-1}}
\end{equation}
and
$$
\frac{p_{k-2}}{q_{k-2}} - \frac{p_k}{q_k} =
\frac{(-1)^ka_k}{q_kq_{k-2}}.
$$
Since all the numbers $q_k$ and $a_k$ are positive, the above
formulas imply the following.

\begin{prop} \label{propord}
The subsequence of convergents $p_k/q_k$ for even indices $k$ is increasing. \\
The subsequence of convergents $p_k/q_k$ for odd indices $k$ is decreasing. \\
Every convergent with an odd index is bigger than every convergent
with an even index.
\end{prop}


{\sl Remark.} Proposition \ref{propord} implies that both
subsequences of convergents (those with odd indices and those with
even indices) have limits. This is a step towards making sense out
of an infinite continued fraction: this should be {\sl common} limit
of these two subsequences. It is somehow more technically involved
(although still fairly elementary!) to prove that these two limits
coincide.


\begin{theorem} \label{inequ}
Let $\alpha=[a_0;a_1,a_2,\ldots, a_n]$. For $k<n$ we have
$$
\frac{1}{q_k(q_{k+1}+q_k)} \leq \left\vert \alpha - \frac{p_k}{q_k}
\right\vert \leq \frac{1}{q_kq_{k+1}}
$$
\end{theorem}
{\sl Proof.}



Another inequality, which provides the lower bound for the distance
between the number $\alpha$ and $k$-th convergent is slightly more
involved. To prove it we first consider the following way to add
fractions which students sometimes prefer.

\begin{Def}
The number
$$
\frac{a+c}{b+d}
$$
is called the mediant of the two fractions $a/b$ and $c/d$. (The
quantities $a,b,c$ and $d$ are integers.)
\end{Def}

\begin{lemma} \label{medi}
If
$$
\frac{a}{b} \leq \frac{c}{d}
$$
then
$$
\frac{a}{b} \leq \frac{a+c}{b+d} \leq \frac{c}{d}.
$$
\end{lemma}



Consider now the sequence of fractions
\begin{equation} \label{seq}
\frac{p_k}{q_k}, \ \frac{p_k+p_{k+1}}{q_k+q_{k+1}}, \
\frac{p_k+2p_{k+1}}{q_k+2q_{k+1}}, \ldots,
\frac{p_k+a_kp_{k+1}}{q_k+a_kq_{k+1}}=\frac{p_{k+2}}{q_{k+2}},
\end{equation}
where the last equality follows from (\ref{main}).


It follows that the sequence  (\ref{seq}) is increasing if $k$ is
even and is decreasing if $k$ is odd. Thus, in particular, the
fraction
\begin{equation} \label{l6}
\frac{p_k+p_{k+1}}{q_k+q_{k+1}}
\end{equation}
is between the quantities $p_k/q_k$ and $\alpha$. Therefore the
distance between
 $p_k/q_k$  and the fraction (\ref{l6}) is smaller than the distance
between  $p_k/q_k$ and $\alpha$:
$$
\left\vert \alpha - \frac{p_k}{q_k} \right\vert \geq
\frac{p_k+p_{k+1}}{q_k+q_{k+1}} = \frac{1}{q_k(q_k + q_{k+1})}.
$$
The second (right) inequality in Theorem \ref{inequ} is now
proved. This finishes the proof of Theorem \ref{inequ}.\\
\textbf{Exercises}
\begin{enumerate}
\item{Check the assertion of Theorem \ref{MAIN} for $k=2$.}\item{
Check that for $k=2$
$$
p_2q_1 - q_2p_1 = -1.
$$
{\sl Hint.} Introduce formally $p_{-1}=1$ and $q_{-1}=0$, check that
then formulas \ref{main} are true also for $k=1$.}

\item{ Combine the previous exercises with (\ref{l5}) to obtain
$$
q_kp_{k-1}-p_kq_{k-1} = (-1)^k
$$
for $k \geq 1$. Derive from this that  $q_k$ and $p_k$ are
relatively prime. }\item{Prove Proposition \ref{propord}}\item{
Combine (\ref{dif1}) with Proposition \ref{propord} to prove the
inequality
$$
\left\vert \alpha - \frac{p_k}{q_k} \right\vert \leq
\frac{1}{q_kq_{k+1}}.
$$
} \item{Prove Lemma \ref{medi}}\item{Use (\ref{main}) to show that
the sign of the difference between two consecutive fractions in
(\ref{seq}) depends only on the parity of $k$.}
\end{enumerate}
\section{Very Good Approximation}

Continued fractions provide a representation of numbers which is, in
a sense, generic and canonical. It does not depend on an arbitrary
choice of a base. Such a representation should be the best in a
sense. In this section we quantify this naive idea. \index{Good
Approximation}
\begin{Def}
A rational number $a/b$ is referred to as a "good" approximation to
a number $\alpha$ if
$$
\frac{c}{d} \neq \frac{a}{b} \hspace{5mm} \text{and} \hspace{5mm}
0<d \leq b
$$
imply
$$
|d\alpha - c| > |b\alpha -a|.
$$
\end{Def}
{\sl Remarks.} 1. Our "good approximation" is "the best
approximation of the second kind" \index{best approximation}
in a more usual terminology. \\
2. Although we use this definition only for rational $\alpha$, it
may be used for any real $\alpha$ as well. Neither the results of
this section nor the proofs
alter. \\
3. Naively, this definition means that $a/b$ approximates $\alpha$
better then any other rational number whose denominator does not
exceed $b$. There is another, more common, definition of "the best
approximation". A rational number $x/y$ is referred to as "the best
approximation of the first kind" if $c/d\neq x/y$ and $0<d\leq y$
imply $|\alpha - c/d|>|\alpha - x/y|$. In other words, $x/y$ is
closer to $\alpha$ than any rational number whose denominator does
not exceed $y$. In our definition we consider a slightly different
measure of approximation, which takes into the account the
denominator, namely $b|\alpha - a/b|=|b\alpha -a|$ instead of taking
just the distance $|\alpha - a/b|$.

\begin{theorem} \label{good}
Any "good" approximation is a convergent.
\end{theorem}

{\sl Proof.} Let $a/b$ be a "good" approximation to $\alpha =
[a_0;a_1,a_2,\ldots,a_n]$. We have to prove that $a/b=p_k/q_k$ for
some $k$.


Thus we have $a/b>p_1/q_1$ or $a/b$ lies between two consecutive
convergents $p_{k-1}/q_{k-1}$ and $p_{k+1}/q_{k+1}$ for some $k$.
Assume the latter. Then
$$
\left\vert \frac{a}{b} - \frac{p_{k-1}}{q_{k-1}} \right\vert \geq
\frac{1}{bq_{k-1}}
$$
and
$$
\left\vert \frac{a}{b} - \frac{p_{k-1}}{q_{k-1}} \right\vert <
\left\vert \frac{p_k}{q_k} - \frac{p_{k-1}}{q_{k-1}} \right\vert =
\frac{1}{q_kq_{k-1}}.
$$
It follows that
\begin{equation} \label{l7}
b>q_k.
\end{equation}
Also
$$
\left\vert \alpha - \frac{a}{b} \right\vert \geq \left\vert
\frac{p_{k+1}}{q_{k+1}} - \frac{a}{b} \right\vert \geq
\frac{1}{bq_{k+1}},
$$
which implies
$$
\left\vert b\alpha - a \right\vert \geq \frac{1}{q_{k+1}}.
$$
At the same time Theorem \ref{inequ} (it right inequality multiplied
by $q_k$) reads
$$
\left\vert q_k \alpha - p_k \right\vert \leq \frac{1}{q_{k+1}}.
$$
It follows that
$$
\left\vert q_k \alpha - p_k \right\vert \leq \left\vert b\alpha - a
\right\vert,
$$
and the latter inequality together with (\ref{l7}) show that $a/b$
is not a "good" approximation of $\alpha$ in this case.


This finishes the proof of Theorem \ref{good}. \\
\textbf{Exercises}
\begin{enumerate}
\item{Prove that if $a/b$ is a "good" approximation then $a/b \geq
a_0$.}\item{Show that if $a/b>p_1/q_1$ then $a/b$ is not a "good"
approximation to $\alpha$.}
\end{enumerate}
\section{An Application}

Consider the following problem which may be of certain practical
interest. Assume that we calculate certain quantity using a
computer. Also assume that we know in advance that the quantity in
question is a rational number. The computer returns a decimal which
has high accuracy and is pretty close to our desired answer. How to
guess the exact answer?

To be more specific consider an example.
\begin{example}

Assume that the desired answer is
$$
\frac{123456}{121169}
$$
and the result of computer calculation with a modest error of
$10^{-15}$ is
$$
\begin{array}{l}
\alpha = 123456/121169 + 10^{-15} = \\
1.01887446459077916933374047817511079566555802226642127937013592 \\
5855623137931319066757999158200529838490042832737746453300761745 \\
9911363467553582186862976503891259315501489654944746593600673439576129207
\end{array}
$$
with some two hundred digits of accuracy which, of course come short
to help in guessing the period and the exact denominator of
$121169$.

\end{example}

Solution. Since $123456/121169$ is a good (just in a naive sense)
approximation to $\alpha$, it should be among its convergents. This
is not an exact statement, but it offers a hope! We have
$$
\alpha = [1; 52, 1, 53, 2, 4, 1, 2, 1, 68110, 4, 1, 2, 106, 22, 3,
1, 1, 10, 2, 1, 3, 1, 3, 4, 2, 11].
$$

We are not going to check all convergents, because we notice the
irregularity: one element, $68110$ is far more than the others. In
order to explain this we use the left inequality from Theorem
\ref{inequ} together with the formula (\ref{main}). Indeed, we have
an approximation of $\alpha$ which is unexpectedly good: $\vert
\alpha - p_k/q_k \vert$ is very small (it is around $10^{-15}$) and
with a modest $q_k$ too. We have
$$
q_k(q_{k+1} + q_k) = q_k(a_{k+1} q_k + q_{k-1}) = q_k^2(a_{k+1} +
q_{k-1}/q_k)
$$
and
$$
\left\vert \alpha - \frac{p_k}{q_k} \right\vert \geq
\frac{1}{q_k^2(a_{k+1} + q_{k-1}/q_k)}.
$$
It follows that $1/q_k^2(a_{k+1} + q_{k-1}/q_k)$ is small (smaller
than $10^{-15}$) and therefore, $a_{k+1}$ should be big. This is
exactly what we see. Of course, our guess is correct:
$$
\frac{123456}{121169} = [1, 52, 1, 53, 2, 4, 1, 2, 1].
$$

In this way we conclude that in general an unexpectedly big element
allows to cut the continued fraction (right before this element) and
to guess the exact rational quantity. There is probably no need
(although this is, of course, possible) to quantify this procedure.
I prefer to use it just for guessing the correct quantities on the
spot from the first glance.


\section{A Formula of Gauss, a Theorem of Kuzmin and L\'evi
and a Problem of Arnold} \index{Kuzmin} \index{Gauss} In this
connection Gauss asked about a probability $c_k$ for a number $k$ to
appear as an element of a continued fraction. Such a probability is
defined in a natural way: as a limit when $N \rightarrow \infty$ of
the number of occurrences of $k$ among the first $N$ elements of the
continued fraction enpension. Moreover, Gauss provided an answer,
but never published the proof. Two different proofs were found
independently by R.O.Kuzmin (1928) and P. L\'evy (1929) (see
\cite{Khinchin} for a detailed exposition of the R.O.Kuzmin's
proof). \index{Probability}

\begin{theorem} \label{Gauss}
For almost every real $\alpha$ the probability for a number $k$ to
appear as an element in the continued fraction expansion of $\alpha$
is
\begin{equation} \label{ga}
c_k=\frac{1}{\ln 2} \ln \left( 1 + \frac{1}{k(k+2)} \right).
\end{equation}
\end{theorem}

{\sl Remarks.} 1. The words "for almost every $\alpha$" mean that
the measure of the set of exceptions is zero. \\
2. Even the existence of $p_k$ (defined as a limit) is highly
non-trivial.



Theorem \ref{Gauss} may (and probably should) be considered as a
result from ergodic theory rather than number theory. This
constructs a bridge between these two areas of Mathematics and
explains the recent attention to continued fractions of the
mathematicians who study dynamical systems. In particular,
V.I.Arnold formulated the following open problem.
\index{Arnold}Consider the set of pairs of integers $(a,b)$ such
that the corresponding points on the plane are contained in a
quarter of a circle of radii $N$:
$$
a^2 + b^2 \leq N^2.
$$
Expand the numbers $p/q$ into continued fractions and compute the
frequencies $s_k$ for the appearance of $k$ in these fractions. Do
these frequencies have limits as $N \rightarrow \infty$? If so, do
these limits have anything to do with the probabilities, given by
(\ref{ga})? These questions demand nothing but experimental computer
investigation, and such an experiment may be undertaken by a
student. Of course, it would be extremely challenging to find a
phenomena experimentally in this way and to prove it after that
theoretically. \par Of course, one can consider more general kinds
of continued fractions. In particular, one may ease the assumption
that the elements are positive integers and consider, allowing
arbitrary reals as the elements (the question of convergence may
usually be solved). The following identities were discovered
independently by three prominent mathematicians. The English
mathematician R.J. Rogers found and proved these identities in 1894,
Ramanujan found the identities (without proof) and formulated them
in his letter to Hardy from India in 1913. Independently, being
separated from England by the war, I. J. Schur found the identities
and published two different proofs in 1917. We refer an interested
reader to \cite{Andrews} for a detailed discussion and just state
the amazing identities here.
$$
[0;e^{-2\pi},e^{-4\pi},e^{-6\pi},e^{-8\pi}, \ldots ]=
\left(\sqrt{\frac{5+\sqrt{5}}{2}} - \frac{\sqrt{5}+1}{2} \right)
e^{2\pi/5}
$$

$$
[1;e^{-\pi},e^{-2\pi},e^{-3\pi},e^{-4\pi}, \ldots ]=
\left(\sqrt{\frac{5-\sqrt{5}}{2}} - \frac{\sqrt{5}-1}{2} \right)
e^{\pi/5}
$$
\textbf{Exercises}
\begin{enumerate}
\item{Prove that $c_k$ really define a probability distribution,
namely that
$$
\sum_{k=1}^\infty c_k =1.
$$
}
\end{enumerate}

\chapter{Introduction to Analytic Number Theory}
\index{Analytic Number Theory} The distribution of prime numbers has
been the object of intense study by many modern mathematicians.
Gauss and Legendre conjectured the prime number theorem which states
that the number of primes less than a positive number $x$ is
asymptotic to $x/log x$ as $x$ approaches infinity.   This
conjecture was later proved by Hadamard and Poisson.  Their proof
and many other proofs lead to the what is known as Analytic Number
theory.
\par In this chapter we demonstrate elementary theorems on primes
and prove elementary properties and results that will lead to the
proof of the prime number theorem.
\section{Introduction}
It is well known that the harmonic series
$\sum_{n=1}^{\infty}\frac{1}{n}$ diverges.  We therefore determine
some asymptotic formulas that determines the growth of the
$\sum_{n\leq x}\frac{1}{n}$.  We start by introducing Euler's
summation formula that will help us determine the asymptotic
formula.

\par We might ask the following question. What if the sum is taken
over all the primes. In this section, we show that the sum over the
primes diverges as well. We also show that an interesting product
will also diverge. From the following theorem, we can actually
deduce that there are infinitely many primes.\\
\\
\index{Euler Summation Formula} \textbf{Euler's Summation Formula}
If $f$ has a continuous derivative on an interval $[a,b]$ where $a>
0$, then
\begin{equation*}
\sum_{a<n\leq
b}f(n)=\int_{a}^bf(t)dt+\int_{a}^b(\{t\})f'(t)dt+f(b)(\{b\})-f(a)(\{a\}).
\end{equation*}
where $\{t\}$ denotes the fractional part of $t$.\\
\\ For the proof of Euler's summation formula see \cite[Chapter
3]{Apostol}.
\begin{prop}
If $x\geq 1$, we have that:
\begin{equation*}
\sum_{n\leq x}\frac{1}{n}=\log x+\gamma+O\left(\frac{1}{x}\right)
\end{equation*}
\end{prop}
\begin{proof}
We use Euler's summation formula by taking $f(t)=1/t$.  We then get
\begin{eqnarray*}
\sum_{n\leq
x}\frac{1}{n}&=&\int_{1}^x\frac{1}{t}dt-\int_1^x\frac{\{t\}}{t^2}dt+1+O\left(\frac{1}{x}\right)\\
&=& \log
x+1-\int_1^{\infty}\frac{\{t\}}{t^2}dt+\int_x^{\infty}\frac{\{t\}}{t^2}dt+O\left(\frac{1}{x}\right)
\end{eqnarray*}
Notice now that $\{t\}\leq t$ and hence the two improper integrals
exist since they are dominated by integrals that converge. We
therefore have
\begin{equation*}
0\leq \int_x^\infty\frac{\{t\}}{t^2}dt\leq \frac{1}{x},
\end{equation*}
we also let \index{Euler Constant}
\begin{equation*}
\gamma=1-\int_1^{\infty}\frac{\{t\}}{t^2}dt
\end{equation*}
and we get the asymptotic formula.  Notice that $\gamma$ is called
Euler's constant.\index{Euler's Constant}  Notice also that similar
steps can be followed to find an asymptotic formulas for other sums
involving powers of $n$.
\par We now proceed to show that if we sum over the primes instead,
we still get a divergent series.
\end{proof}
\begin{theorem}
Both $\sum_p\frac{1}{p}$ and $\prod_p(1-\frac{1}{p})$ diverge.
\end{theorem}
\begin{proof}
Let $x \geq 2$ and put
\begin{equation*}
P(x)=\prod_{p\leq x}\left(1-\frac{1}{p}\right)^{-1}, \ \ \
S(x)=\sum_{p\leq x}\frac{1}{p}
\end{equation*}
Let $0<u<1$ and $m\in \mathbb{Z}$, we have
\begin{equation*}
\frac{1}{1-u}>\frac{1-u^{m+1}}{1-u}=1+u+...+u^m.
\end{equation*}
Now taking $u=\frac{1}{p}$, we get
\begin{equation*}
\frac{1}{1-\frac{1}{p}}>1+\frac{1}{p}+...+\left(\frac{1}{p}\right)^m
\end{equation*}
As a result, we have that
\begin{equation*}
P(x)>\prod_{p\leq x}\left(1+\frac{1}{p}+...+\frac{1}{p^m}\right)
\end{equation*}
Choose $m>0 \in \mathbb{Z}$ such that $2^{m-1}\leq x\leq 2^m$.
Observe also that
\begin{equation*}
\prod_{p\leq
x}\left(1+\frac{1}{p}+...+\frac{1}{p^m}\right)=1+\sum_{p_i\leq
x}\frac{1}{p_1^{m_1}p_2^{m_2}...}
\end{equation*}
where $1\leq m_i\leq m$ .  As a result, we get every $\frac{1}{n},
n\in \mathbb{Z^+}$ where each prime factor of $n$ is less than or
equal to $x$(Exercise). Thus we have
\begin{equation*}
\prod_{p\leq
x}\left(1+\frac{1}{p}+...+\frac{1}{p^m}\right)>\sum_{n=1}^{2^{m-1}}\frac{1}{n}>\sum_{n=1}^{[x/2]}\frac{1}{n}
\end{equation*}
Taking the limit as $x$ approaches infinity, we conclude that $P(x)$
diverges.
\par We proceed now to prove that $S(x)$ diverges.  Notice that if
$u>0$, then
\begin{equation*}
\log(1/u-1)<u+\frac{1}{2}(u^2+u^3+...).
\end{equation*}
Thus we have
\begin{equation*}
\log(1/u-1)<u+\frac{u^2}{2}(1/1-u), \ \ \ 0<u<1.
\end{equation*}
We now let $u=1/p$ for each $p\leq x$, then
\begin{equation*}
\log\left(\frac{1}{1-1/p}\right)-\frac{1}{p}<\frac{1}{2p(p-1)}
\end{equation*}
Thus
\begin{equation*}
\log P(x)=\sum_{p\leq x}log(1/1-p).
\end{equation*}
Thus we have
\begin{equation*}
\log P(x)-S(x)<\frac{1}{2}\sum_{p\leq
x}\frac{1}{p(p-1)}<\frac{1}{2}\sum_{n=1}^{\infty}\frac{1}{n(n-1)}
\end{equation*}
This implies that
\begin{equation*}
S(x)>\log  P(x)-\frac{1}{2}
\end{equation*}
And thus $S(x)$ diverges as $x$ approaches infinity.
\end{proof}
\index{Abel Summation Formula}
\begin{theorem}[Abel's Summation Formula]\label{1}
For any arithmetic function $f(n)$, we let
\begin{equation*}
A(x)=\sum_{n\leq x}f(n)
\end{equation*}
where $A(x)=0$ for $x<1$.  Assume also that $g$ has a continuous
derivative on the interval $[y,x]$, where $0<y<x$.  Then we have
\begin{equation*}
\sum_{y<n\leq x}f(n)g(n)=A(x)g(x)-A(y)g(y)-\int_y^xA(t)g'(t)dt.
\end{equation*}
\end{theorem}
The proof of this theorem can be found in \cite[Chapter
4]{Apostol}.\\ \textbf{Exercises}
\begin{enumerate}
\item{Show that one gets every $\frac{1}{n},
n\in \mathbb{Z^+}$ where each prime factor of $n$ is less than or
equal to $x$ in the proof of Theorem 1.}\item{Write down the proof
of Abel's summation formula in details.}
\end{enumerate}
\section{Chebyshev's Functions} \index{Chebyshev's Functions}
We introduce some number theoretic functions which play important
role in the distribution of primes.  We also prove analytic results
related to those functions. We start by defining the Van-Mangolt
function \index{Van-Mangolt Function}
\begin{def1}
$\Omega(n)=logp$ if $n=p^m$ and vanishes otherwise.
\end{def1}
We define also the following functions, the last two functions are
called Chebyshev's functions.
\begin{enumerate}
\item{$\pi(x)=\sum_{p\leq x}1.$}\item{$\theta(x)=\sum_{p\leq x}log
p$}\item{$\psi(x)=\sum_{n\leq x}\Omega(n)$}
\end{enumerate}
Notice that
\begin{equation*}
\psi(x)=\sum_{n\leq x}\Omega(n)=\sum_{m=1, \ p^m\leq
x}^{\infty}\sum_p\Omega(p^m)=\sum_{m=1}^{\infty}\sum_{p\leq
x^{1/m}}log p.
\end{equation*}
\begin{example}
\begin{enumerate}
\item{$\pi(10)=4$.} \item{$\theta(10)=log 2+ log 3+ log 5+log
7$.}\item{$\psi(10)=log 2+ log 2+log 2+ log 3+ log 3+ log 5+ log 7$}
\end{enumerate}
\end{example}
\begin{remark}
It is easy to see that
\begin{equation*}
\psi(x)=\theta(x)+\theta(x^{1/2})+
\theta(x^{1/3})+...\theta(x^{1/m})
\end{equation*}
where $m\leq log_2x$.  This remark is left as an exercise.
\end{remark}
Notice that the above sum will be a finite sum since for some $m$,
we have that $x^{1/m}<2$ and thus $\theta(x^{1/m})=0$.\\
We use Abel's summation formula now to express the two functions
$\pi(x)$ and $\theta(x)$  in terms of integrals.
\begin{theorem}
For $x\geq 2$, we have
\begin{equation*}
\theta(x)=\pi(x)\log x-\int_ {2}^{x}\frac{\pi(t)}{t}dt
\end{equation*}
and
\begin{equation*}
 \pi(x)=\frac{\theta(x)}{\log x}+\int_{2}^x\frac{\theta(t)}{t\log^2t}dt.
 \end{equation*}
\end{theorem}
\begin{proof}
We define the characteristic function $\chi(n)$ to be $1$ if $n$ is
prime and $0$ otherwise.  As a result, we can see from the
definition of $\pi(x)$ and $\theta(x)$ that they can be represented
in terms of the characteristic function $\chi(n)$.  This
representation will enable use to apply Abel's summation formula
where $f(n)=\chi(n)$ for $\theta(x)$ and where $f(n)=\chi(n) \log n$
for $\pi(x)$.  So we have,
\begin{equation*}
\pi(x)=\sum_{1\leq n/leq x}\chi(n) \ \ \ \  \mbox{and} \ \ \
\theta(x)=\sum_{1\leq n\leq x}\chi(n)\log n
\end{equation*}
Now let $g(x)=\log x$ in Theorem 84 with $y=1$ and we get the
desired result for the integral representation of $\theta(x)$.
Similarly we let $g(x)=1/\log x$ with $y=3/2$ and we obtain the
desired result for $\pi(x)$ since $\theta(t)=0$ for $t<2$.
\end{proof}
\par We now prove a theorem that relates the two Chebyshev's
functions $\theta(x)$ and $\psi(x)$.  The following theorem states
that if the limit of one of the two functions $\theta(x)/x$ or
$\psi(x)/x$ exists then the limit of the other exists as well and
the two limits are equal.
\begin{theorem}
For $x>0$, we have
\begin{equation*}
0 \leq \frac{\psi(x)}{x}-\frac{\theta(x)}{x}\leq \frac{(\log
x)^2}{2\sqrt{x}\log 2}.
\end{equation*}
\end{theorem}
\begin{proof}
From Remark 4, it is easy to see that
\begin{equation*}
0\leq \psi(x)-\theta(x)=\theta(x^{1/2})+
\theta(x^{1/3})+...\theta(x^{1/m})
\end{equation*}
where $m\leq log_2x$.  Moreover, we have that $\theta(x)\leq x\log
x$.  The result will follow after proving the inequality in Exercise
2.
\end{proof}
\textbf{Exercises}
\begin{enumerate}
\item{Show that \begin{equation*}
\psi(x)=\theta(x)+\theta(x^{1/2})+
\theta(x^{1/3})+...\theta(x^{1/m})
\end{equation*}
where $m\leq log_2x$.}
\item{Show that $0\leq \psi(x)-\theta(x)\leq (\log_2(x))\sqrt{x}\log\sqrt{x}$ and thus the result of Theorem 86 follows.}
\item{Show that the following two relations are equivalent
\begin{equation*}
\pi(x)=\frac{x}{\log x}+O\left(\frac{x}{\log^2x}\right)
\end{equation*}
\begin{equation*}
\theta(x)=x+O\left(\frac{x}{\log x}\right)
\end{equation*}}
\end{enumerate}
\section{Getting Closer to the Proof of the Prime Number Theorem}

We know prove a theorem that is related to the defined functions
above.  Keep in mind that the prime number theorem is given as
follows:
\begin{equation*}
\lim_{x \rightarrow \infty} \frac{\pi(x)logx}{x}=1.
\end{equation*}
We now state equivalent forms of the prime number theorem.
\begin{theorem}
The following relations are equivalent
\begin{equation}\label{3}
\lim_{x\rightarrow \infty}\frac{\pi(x)\log x}{x}=1
\end{equation}
\begin{equation}\label{4}
\lim_{x\rightarrow \infty} \frac{\theta(x)}{x}= 1
\end{equation}
\begin{equation}\label{5}
\lim_{x\rightarrow \infty} \frac{\psi(x)}{x}= 1.
\end{equation}
\end{theorem}
\begin{proof}
We have proved in Theorem 86 that $(\ref{4})$ and $(\ref{5})$ are
equivalent, so if we show that $(\ref{3})$ and $(\ref{4})$ are
equivalent, the proof will follow.  Notice that using the integral
representations of the functions in Theorem 85, we obtain
\begin{equation*}
\frac{\theta(x)}{x}=\frac{\pi(x)\log x}{x}-\frac{1}{x}\int_
{2}^{x}\frac{\pi(t)}{t}dt
\end{equation*}
and
\begin{equation*}
 \frac{\pi(x)\log x}{x}=\frac{\theta(x)}{x}+\frac{\log x}{x}\int_{2}^x\frac{\theta(t)}{t\log^2t}dt.
 \end{equation*}
Now to prove that (\ref{3}) implies $(\ref{4})$, we need to prove
that
\begin{equation*}
\lim_{x\rightarrow \infty}\frac{1}{x}\int_
{2}^{x}\frac{\pi(t)}{t}dt=0.
\end{equation*}
Notice also that $(\ref{3})$ implies that
$\frac{\pi(t)}{t}=O\left(\frac{1}{\log t}\right)$ for $t\geq 2$ and
thus we have
\begin{equation*}
\frac{1}{x}\int_
{2}^{x}\frac{\pi(t)}{t}dt=O\left(\frac{1}{x}\int_2^x\frac{dt}{\log
t}\right)
\end{equation*}
Now once you show that (Exercise 1)
\begin{equation*}
\int_2^x\frac{dt}{\log t}\leq \frac{\sqrt{x}}{\log
2}+\frac{x-\sqrt{x}}{\log \sqrt{x}},
\end{equation*}
then $(\ref{3})$ implies $(\ref{4})$ will follow. We still need to
show that $(\ref{4})$ implies $(\ref{3})$ and thus we have to show
that
\begin{equation*}
\lim_{x\rightarrow \infty}\frac{\log x}{x}\int_{2}^x
\frac{\theta(t)dt}{t\log^2t}=0.
\end{equation*}
Notice that $\theta(x)=O(x)$ and hence
\begin{equation*}
\frac{\log x}{x}\int_{2}^x
\frac{\theta(t)dt}{t\log^2t}=O\left(\frac{\log
x}{x}\int_2^x\frac{dt}{\log^2t}\right).
\end{equation*}
Now once again we show that (Exercise 2)
\begin{equation*}
\int_2^x\frac{dt}{\log^2t}\leq
\frac{\sqrt{x}}{\log^22}+\frac{x-\sqrt{x}}{\log^2\sqrt{x}}
\end{equation*}
then $(\ref{4})$ implies $(\ref{3})$ will follow.

\end{proof}
\begin{theorem}
Define
\begin{equation*}
l_1=\liminf_{x\rightarrow \infty}\frac{\pi(x)}{x/log x}, \ \ \ \ \
L_1=\limsup_{x\rightarrow \infty}\frac{\pi(x)}{x/log x},
\end{equation*}
\begin{equation*}
l_2=\liminf_{x\rightarrow \infty}\frac{\theta(x)}{x}, \ \ \ \ \
L_2=\limsup_{x\rightarrow \infty}\frac{\theta(x)}{x},
\end{equation*}
and
\begin{equation*}
l_3=\liminf_{x\rightarrow \infty}\frac{\psi(x)}{x}, \ \ \ \ \
L_3=\limsup_{x\rightarrow \infty}\frac{\psi(x)}{x},
\end{equation*}
then $l_1=l_2=l_3$ and $L_1=L_2=L_3$.
\end{theorem}
\begin{proof}
Notice that
\begin{equation*}
\psi(x)=\theta(x)+\theta(x^{1/2})+
\theta(x^{1/3})+...\theta(x^{1/m})\geq \theta(x)
\end{equation*}
where $m\leq log_2x$
\end{proof}
Also,
\begin{equation*}
\psi(x)=\sum_{p\leq x}\left[\frac{\log x}{\log p}\right]\log p\leq
\sum_{p\leq x}\frac{\log x}{\log p} \log p= \log x\pi(x).
\end{equation*}
Thus we have
\begin{equation*}
\theta(x)\leq \psi(x)\leq \pi(x)\log x
\end{equation*}
As a result, we have
\begin{equation*}
\frac{\theta(x)}{x}\leq \frac{\psi(x)}{x}\leq \frac{\pi(x)}{x/\log
x}
\end{equation*}
and we get that $L_2\leq L_3\leq L_1$. We still need to prove that
$L_1 \leq  L_2$.
\par Let $\alpha$ be a real number where $0<\alpha<1$, we have
\begin{eqnarray*}
\theta(x)&=&\sum_{p\leq x}\log p\geq \sum_{x^{\alpha}\leq p\leq
x}\log p\\ &>& \sum_{x^{\alpha}\leq p\leq x}\alpha \log x  \ \ \
(\log p>\alpha \log x)\\ &=&\alpha log x\{\pi(x)-\pi(x^{\alpha})\}
\end{eqnarray*}
However, $\pi(x^{\alpha})\leq x^{\alpha}$. Hence
\begin{equation*}
\theta(x)>\alpha \log x\{\pi(x)-x^{\alpha}\}
\end{equation*}
As a result,
\begin{equation*}
\frac{\theta(x)}{x} > \frac{\alpha \pi(x)}{x/ \log x}- \alpha
x^{\alpha-1}\log x
\end{equation*}
Since $\lim_{x\rightarrow \infty}\alpha \log x/x^{1-\alpha}=0$, then
\begin{equation*}
L_2\geq \alpha \limsup_{x\rightarrow \infty}\frac{\pi(x)}{x/\log x}
\end{equation*}
As a result, we get that
\begin{equation*}
L_2\geq \alpha L_1
\end{equation*}
As $\alpha \rightarrow 1$, we get $L_2\geq L_1$.

\par Proving that $l_1=l_2=l_3$ is left as an exercise.

We now present an inequality due to Chebyshev about $\pi(x)$.
\begin{theorem}
There exist constants $a<A$ such that
\begin{equation*}
a\frac{x}{\log x}<\pi(x)<A\frac{x}{\log x}
\end{equation*}
for sufficiently large $x$.
\end{theorem}
\begin{proof}
Put
\begin{equation*}
l=\liminf_{x\rightarrow \infty}\frac{\pi(x)}{x/\log x}, \ \ \ \ \
L=\limsup_{x\rightarrow \infty}\frac{\pi(x)}{x/\log x},
\end{equation*}
It will be sufficient to prove that $L\leq 4 \log 2$ and $l\geq \log
2$.  Thus by Theorem 2, we have to prove that
\begin{equation}\label{1}
\limsup_{x\rightarrow \infty}\frac{\theta(x)}{x}\leq 4 \log 2
\end{equation}
and
\begin{equation}\label{2}
\liminf_{x\rightarrow \infty}\frac{\psi(x)}{x}\geq \log 2
\end{equation}
To prove ($\ref{1}$), notice that
\begin{equation*}
N=C(2n,n)=\frac{(n+1)(n+2)...(n+n)}{n!}<2^{2n}<(2n+1)N
\end{equation*}
Suppose now that $p$ is a prime such that $n<p<2n$ and hence $p\mid
N$. As a result, we have $N \geq \prod_{n<p<2n}p$. We get
\begin{equation*}
N\geq \theta(2n)-\theta(n).
\end{equation*}
Since $N<2^{2n}$, we get that $\theta(2n)-\theta(n)<2n\log 2$. Put
$n=1,2,2^2,...,2^{m-1}$ where $m$ is a positive integer.  We get
that
\begin{equation*}
\theta(2^m)<2^{m-1}\log 2.
\end{equation*}
Let $x>1$  and choose $m$ such that $2^{m-1}\leq x\leq 2^m$, we get
that
\begin{equation*}
\theta(x)\leq \theta(2^m)\leq 2^{m+1}\log 2 \leq 4x\log 2
\end{equation*}
and we get $(\ref{1})$ for all $x$.
\par We now prove $(\ref{2})$.
Notice that by Lemma 9, we have that the highest power of a prime
$p$ dividing $N=\frac{(2n)!}{(n!)^2}$ is given by
\begin{equation*}
s_p=\sum_{i=1
1}^{\mu_p}\left\{\left[\frac{2n}{p^i}\right]-2\left[\frac{n}{p^i}\right]\right\}.
\end{equation*}
where $\mu_p=\left[\frac{\log 2n}{\log p}\right]$. Thus we have
$N=\prod_{p\leq 2n}p^{s_p}$. If $x$ is a positive integer then
\begin{equation*}
[2x]-2[x]<2,
\end{equation*}
It means that $[2x]-2[x]$ is $0$ or $1$.  Thus $s_p\leq \mu_p$ and
we get
\begin{equation*}
N\leq \prod_{p\leq e2n}p^{\mu_p}.
\end{equation*}
Notice as well that
\begin{equation*}
\psi(2n)=\sum_{p\leq 2n}\left[\frac{\log 2n}{\log p}\right]\log
p=\sum_{p\leq 2n}\mu_p \log p.
\end{equation*}
Hence we get
\begin{equation*}
\log N \leq \psi(2n).
\end{equation*}
Using the fact that $2^{2n}<(2n+1)N$, we can see that
\begin{equation*}
\psi(2n)>2n \log 2-\log (2n+1).
\end{equation*}
Let $x>2$ and put $n=\left[\frac{x}{2}\right]\geq 1$.  Thus
$\frac{x}{2}-1<n<\frac{x}{2}$ and we get $2n \leq x$. So we get
\begin{eqnarray*}
\psi(x)&\geq &\psi(2n)>2n \log 2- \log (2n+1)\\&>&(x-2)\log 2- \log
(x+1).
\end{eqnarray*}
As a result, we get
\begin{equation*}
\liminf_{x\rightarrow \infty}\frac{\psi(x)}{x}\geq \log 2.
\end{equation*}
\end{proof}


\textbf{Exercises}
\begin{enumerate}
\item{Show that $l_1=l_2=l_3$ in Theorem 88.}
\item{ Show that \begin{equation*}
\int_2^x\frac{dt}{\log t}\leq \frac{\sqrt{x}}{\log
2}+\frac{x-\sqrt{x}}{\log \sqrt{x}},
\end{equation*}}
\item{Show that \begin{equation*}
\int_2^x\frac{dt}{\log^2t}\leq
\frac{\sqrt{x}}{\log^22}+\frac{x-\sqrt{x}}{\log^2\sqrt{x}}
\end{equation*}}
\item{Show that \begin{equation*}
N=C(2n,n)=\frac{(n+1)(n+2)...(n+n)}{n!}<2^{2n}<(2n+1)N
\end{equation*}}
\item{Show that $\frac{2^{2n}}{2\sqrt{n}}<N=C(2n,n)< \frac{2^{2n}}{\sqrt{2n}}$. \\ Hint: For one side of the inequality,
write
\begin{equation*}
\frac{N}{2^n}=\frac{(2n)!}{2^{2n}(n!)^2}=\frac{1.3.5....(2n-1)}{2.4.6....(2n)}.\frac{2.4.6.....(2n)}{2.4.6...(2n)},
\end{equation*}
then show that
\begin{equation*}
1>(2n+1).\frac{N^2}{2^{4n}}>2n.\frac{N^2}{2^{4n}}.
\end{equation*}
The other side of the inequality will follow with similar arithmetic
techniques as the first inequality.}

\end{enumerate}

\chapter{Other Topics in Number Theory}

This chapter discusses various topics that are of profound interest in number theory. Section 1 on cryptography is on an
application of number theory in the field of message decoding, while the other sections on elliptic curves and the
Riemann zeta function are deeply connected with number theory. The section on Fermat's last theorem is related,
through Wile's proof of Fermat's conjecture on the non-existence of integer solutions to $x^n+y^n=z^n$ for $n>2$, to the
field of elliptic curves (and thus to section 2).


% 1 z q a Q A Z

\section{Cryptography}

% 1 z q a Q A Z
\index{Cryptography} In this section we discuss some elementary
aspects of cryptography, which concerns the coding and decoding of
messages. In cryptography, a (word) message is transformed into a
sequence $a$ of integers, by replacing each letter in the message by
a specific and known set of integers that represent this letter, and
thus forming a large integer $a$ by concatenation. Then this integer
$a$ is transformed (i.e. coded) into another integer $b$ by using a
congruence of the form $b=a^k(mod\ m)$ for some chosen $k$ and $m$,
as described below, with $k$ unknown except to the sender and
receiver. $b$ is then sent to the receiver who decodes it into $a$
again by using a congruence of the form $a=b^{\bar{k}}(mod\ m)$,
where $\bar{k}$ is related to $k$ and is itself only known to the
sender and receiver, and then simply transforms the integers in $a$
back to letters and reveals the message again. In this procedure, if
a third party intercepts the integer $b$, the chance of transforming
this into $a$, even if $m$ and the integers that represent the
letters of the alphabet are exactly known, is almost impossible to
do (i.e. has a fantastically small probability of being achieved) if
$k$ is not known, that practically the transformed message will not
be revealed except to the intended receiver.

The basic results on congruences to allow for the above procedure are in the following two lemmata, where $\phi$ in the
statements is Euler's $\phi$-function.

\begin{lemma}
Let $a$ and $m$ be two integers, with $m$ positive and $(a,m)=1$. If $k$ and $\bar{k}$ are positive integers
with $k\bar{k}=1(mod\ \phi(m))$, then $a^{k\bar{k}}=a(mod\ m)$.
\end{lemma}

\begin{proof}
$k\bar{k}=1(mod\ \phi(m))$ thus $k\bar{k}=q\phi(m)+1$ ($q\geq 0$). Hence $a^{k\bar{k}}=a^{q\phi(m)+1}=a^{q\phi(m)}a$.
But by Euler's Theorem, if $(a,m)=1$ then $a^{\phi(m)}=1(mod\ m)$. This gives that
\begin{equation}
(a^{\phi(m)})^qa=1(mod\ m)a=a(mod\ m),
\end{equation}
and hence that $a^{k\bar{k}}=a(mod\ m)$, and the result follows.
\end{proof}

We also need the following.

\begin{lemma}
Let $m$ be a positive integer, and let $r_1, r_2,\cdots, r_n$ be a reduced residue system
modulo $m$ (i.e. with $n=\phi(m)$ and $(r_i,m)=1$ for $i=1,\cdots,n$). If $k$ is an integer such
that $(k,\phi(m))=1$, then $r_1^k, r_2^k,\cdots, r_n^k$ forms a reduced residue system modulo $m$.
\end{lemma}

Before giving the proof, one has to note that the above lemma is in fact an if-and-only-if statement,
i.e. $(k,\phi(m))=1$ if and only if $r_1^k, r_2^k,\cdots, r_n^k$ forms a reduced residue system modulo $m$.
However we only need the if part, as in the lemma.

\begin{proof}
Assume first that $(k,\phi(m))=1$. We show that $r_1^k, r_2^k,\cdots, r_n^k$ is a reduced residue system modulo $m$.
Assume otherwise, i.e. assume that $\exists i,j$ such that $r_i^k=r_j^k(mod\ m)$, in which case $r_i^k$ and $r_j^k$
would belong to the same class and thus $r_1^k, r_2^k,\cdots, r_n^k$ would not form a reduced residue system.
Then, since $(k,\phi(m))=1$, $\exists\bar{k}$ with $k\bar{k}=1(mod\ \phi(m))$, and so
\begin{equation}
r_i^{k\bar{k}}=r_i(mod\ m)\hspace{0.5cm}and\hspace{0.5cm}r_j^{k\bar{k}}=r_j(mod\ m)
\end{equation}
by the previous lemma. But if $r_i^k=r_j^k(mod\ m)$ then $(r_i^k)^{\bar{k}}=(r_j^k)^{\bar{k}}(mod\ m)$,
and since $r_i^{k\bar{k}}=r_i(mod\ m)$ and $r_j^{k\bar{k}}=r_j(mod\ m)$, then $r_i=r_j(mod\ m)$ giving
that $r_i$ and $r_j$ belong to the same class modulo $m$, contradicting that $r_1, r_2,\cdots, r_n$ form a reduced
residue system. Thus $r_i\neq r_j$ implies that $r_i^k\neq r_j^k$ if $(k,\phi(m))=1$.
\end{proof}

Now to do cryptography, one proceeds as follows. Let $S$ be a sentence given in terms of letters and spaces
between the words that is intended to be transformed to a destination with the possibility of being intercepted
and revealed by a third party.
\begin{enumerate}
\item Transform $S$ into a (large) integer $a$ by replacing each letter and each space between words by a
certain representative integer (e.g. three or four digit integers
for each letter). $a$ is formed by concatenating the representative
integers that are produced.

\item Choose a couple $p_1$ and $p_2$ of very large prime numbers, each (for example) of the order of a hundred
digit integer, and these should be strictly kept known only to the sender and receiver. Then form the product
$m=p_1p_2$, which is itself a very large number to the point that the chances of someone revealing the prime
number factorization $p_1p_2$ of $m$ is incredibly small, even if they know this integer $m$. Now one has, by
standard results concerning the $\phi$-function, that $\phi(p_1)=p_1-1$ and $\phi(p_2)=p_2-1$, and that,
since $p_1$ and $p_2$ are relatively prime, $\phi(m)=\phi(p_1)\phi(p_2)=(p_1-1)(p_2-1)$. Thus $\phi(m)$ is a
very large number, of the order of $m$ itself, and hence $m$ has a reduced residue system that contains a very
large number of integers of the order of $m$ itself. Hence almost every integer smaller than $m$, with a
probability of the order $1-1/10^{100}$ (almost 1), is in a reduced residue system $r_1, r_2,\cdots, r_{\phi(m)}$ of $m$.
Thus almost every positive integer smaller than $m$ is relatively prime with $m$, with probability of the
order $1-1/10^{100}$.

\item Now given that almost every positive integer smaller than $m$ is relatively prime with $m$, the integer $a$
itself is almost certainly relatively prime with $m$, and hence is in a reduced residue system for $m$. Hence, by
lemma 17 above, if $k$ is a (large) integer such that $(k,\phi(m))=1$, then $a^k$ belongs to a reduced residue
system for $m$, and there exists a unique positive $b$ smaller than $m$ with $b=a^k(mod\ m)$.

\item Send $b$ to the destination where $\phi(m)$ and $k$ are known. The destination can determine a $\bar{k}$
such that $k\bar{k}=1(mod\ \phi(m))$, and then finds the unique $c$ such that $c=b^{\bar{k}}(mod\ m)$. Now since,
almost certainly, $(a,m)=1$, then almost certainly $c=a$ since
$c=b^{\bar{k}}(mod\ m)=(a^k)^{\bar{k}}(mod\ m)=a^{k\bar{k}}(mod\ m)$, and which by lemma 16, is given by
 $a(mod\ m)$ almost certainly since $(a,m)=1$ almost certainly. Now the destination translates $a$ back to letters
 and spaces to reveal the sentence $S$. Note that if any third party intercepts $b$, they almost certainly cannot
 reveal the integer $a$ since the chance of them knowing $\phi(m)=p_1p_2$ is almost zero, even if they know $m$ and $k$.
 In this case they practically won't be able to determine a $\bar{k}$ with $k\bar{k}=1(mod\ \phi(m))$, to retrieve $a$
 and transform it to $S$.
\end{enumerate}



\section{Elliptic Curves}
Elliptic curves in the $xy$-plane are the set of points
$(x,y)\in\mathbb{R}\times\mathbb{R}$ that are the zeros of special
types of third order polynomials $f(x,y)$, with real coefficients,
in the two variables $x$ and $y$. These curves turn out to be of
fundamental interest in analytic number theory. More generally, one
can define similar curves over arbitrary algebraic fields as
follows. Let $f(x,y)$ be a polynomial of any degree in two variables
$x$ and $y$, with coefficients in an algebraic field $\mathcal{F}$.
We define the {\it algebraic curve} $\mathscr{C}_f(\mathcal{F})$
over the field $\mathcal{F}$ by
\begin{equation}
\mathscr{C}_f(\mathcal{F})=\{(x,y)\in\mathcal{F}\times\mathcal{F}:f(x,y)=0\in
\mathcal{F}\}.
\end{equation}
Of course one can also similarly define the algebraic curve
$\mathscr{C}_f(\mathcal{Q})$ over a field $\mathcal{Q}$, where
$\mathcal{Q}$ is either a subfield of the field $\mathcal{F}$ where
the coefficients of $f$ exist, or is an extension field of
$\mathcal{F}$. Thus if $f\in\mathcal{F}[x,y]$, and if $\mathcal{Q}$
is either an extension or a subfield of $\mathcal{F}$, then one can
define
$\mathscr{C}_f(\mathcal{Q})=\{(x,y)\in\mathcal{Q}\times\mathcal{Q}:f(x,y)=0\}$.
\index{Cubic Curves} Our main interest in this section will be in
third order polynomials (cubic curves)
\begin{equation}
f(x,y)=ax^3+bx^2y+cxy^2+dy^3+ex^2+fxy+gy^2+hx+iy+j,
\end{equation}
with coefficients in $\mathcal{R}$, with the associated curves
$\mathscr{C}_f(\mathbb{Q})$ over the field of rational numbers
$\mathbb{Q}\subset\mathbb{R}$. Thus, basically, we will be
interested in points $(x,y)\in\mathbb{R}^2$ that have rational
coordinates $x$ and $y$, and called rational points, that satisfy
$f(x,y)=0$. Of course one can first imagine the curve $f(x,y)=0$ in
$\mathbb{R}^2$, i.e. the curve $\mathscr{C}_f(\mathbb{R})$ over
$\mathbb{R}$, and then choosing the points on this curve that have
rational coordinates. This can simply be expressed by writing that
$\mathscr{C}_f(\mathbb{Q})\subset\mathscr{C}_f(\mathbb{R})$.
\index{Rational Curves} It has to be mentioned that "rational
curves" $\mathscr{C}_f(\mathbb{Q})$ are related to diophantine
equations. This is in the sense that rational solutions to equations
$f(x,y)=0$ produce integer solutions to equations $f'(x,y)=0$, where
the polynomial $f'$ is very closely related to the polynomial $f$,
if not the same one in many cases. For example every point in
$\mathscr{C}_f(\mathbb{Q})$,  where $f(x,y)=x^n+y^n$, i.e. every
rational solution to $f(x,y)=x^n+y^n=0$, produces an integer
solution to $x^n+y^n=0$. Thus algebraic curves
$\mathscr{C}_f(\mathbb{Q})$ can be of genuine interest in this
sense.

In a possible procedure to construct the curve $\mathscr{C}_f(\mathbb{Q})$ for a polynomial $f(x,y)\in\mathbb{R}[x,y]$
with real coefficients, one considers the possibility that, given one rational point
$(x,y)\in\mathscr{C}_f(\mathbb{Q})\subset\mathscr{C}_f(\mathbb{R})$, a straight line with a rational slope $m$
might intersect the curve $\mathscr{C}_f(\mathbb{R})$ in a point $(x',y')$ that is also in $\mathscr{C}_f(\mathbb{Q})$.
This possibility comes from the simple fact that if $(x,y), (x',y')\in\mathscr{C}_f(\mathbb{Q})$, then the slope of the
straight line that joins $(x,y)$ and $(x',y')$ is a rational number. This technique, of determining one point in
$\mathscr{C}_f(\mathbb{Q})$ from another by using straight lines as mentioned, works very well in some cases of
polynomials, especially those of second degree, and works reasonably well for third order polynomials.

Two aspects of this technique of using straight lines to determine points in $\mathscr{C}_f(\mathbb{Q})$,
and which will be needed for defining elliptic curves, are the following. The first is illustrated by the
following example.

Consider the polynomial $f(x,y)=y^2-x^2+y=(y-x+1)(y+x)$. The curve
$\mathscr{C}_f(\mathbb{R})$ contains the two straight lines $y=x-1$
and $y=-x$. The point $(2,1)\in\mathscr{C}_f(\mathbb{Q})$, and if
one tries to find the intersection of the particular line $y=x-1$
that passes through $(2,1)$ with $\mathscr{C}_f(\mathbb{R})$, one
finds that this includes the whole line $y=x-1$ itself, and not just
one or two other points (for example). This result is due to the
fact that $f$ is a reducible polynomial, i.e. that can be factored
in the form $f=f'f''$ with $f$ and $f''$ not just real numbers.

In this direction one has the following general theorem concerning the number of intersection points between a straight
line $L$ and an algebraic curve $\mathscr{C}_f(\mathcal{R})$:

\begin{theorem}
If $f\in\mathbb{R}[x,y]$ is a polynomial of degree $d$, and the line $L$, which is defined by the zeros of
 $g(x,y)=y-mx-b\in\mathbb{R}[x,y]$, are such that $L\cap\mathscr{C}_f(\mathcal{R})$ contains more than $d$ points
 (counting the multiplicities of intersections) then in fact
 $L=\mathscr{C}_g(\mathcal{R})\subset\mathscr{C}_f(\mathcal{R})$, and $f$ can be written in the form
 $f(x,y)=g(x,y)p(x,y)$, where $p(x,y)$ is some polynomial of degree $d-1$.
\end{theorem}

In connection with the above theorem, and in defining an elliptic curve $\mathscr{C}_f(\mathcal{R})$,
where $f$ is a polynomial of degree three, we shall require that this curve be such that any straight line that
passes through two points $(x_1,y_1), (x_2,y_2)\in\mathscr{C}_f(\mathcal{R})$, where the two points could be the same
point if the curve at one of them is differentiable with the tangent at that point to the curve having same slope as
that of the line, will also pass through a unique third point $(x_3,y_3)$. By the above theorem, if a line intersects
the curve $\mathscr{C}_f(\mathcal{R})$ associated with the third order polynomial $f$ in more than three points, then
the line itself is a subset of $\mathscr{C}_f(\mathcal{R})$. This will be excluded for the kind of third degree
polynomials $f$ whose associated algebraic curves shall be called elliptic curves.

One other thing to be excluded, to have third order curves characterized as elliptic curves, is the existence of
singular points on the curve, where a singular point is one where the curve does not admit a unique tangent.

It has to be mentioned that in the previous discussion, the points
on the curve $\mathscr{C}_f(\mathbb{R})$ may lie at infinity. To
deal with this situation we assume that the curve is in fact a curve
in the real projective plane $\mathbb{P}_2(\mathbb{R})$.
\index{Elliptic Curve} We now can define an {\bf elliptic curve}
$\mathscr{C}_f(\mathbb{R})$ as being such that $f(x,y)$ is an
irreducible third order polynomial with $\mathscr{C}_f(\mathbb{R})$
having no singular points in $\mathbb{P}_2(\mathbb{R})$.

The main idea behind the above definition for elliptic curves is to have a curve whereby any two points $A$ and $B$
on the curve can determine a {\it unique} third point, to be denoted by $AB$, using a straight line joining $A$ and $B$.
The possibilities are as follows: If the line joining $A$ and $B$ is not tangent to the curve $\mathscr{C}_f(\mathbb{R})$
at any point, then the line intersects the curve in exactly three different points two of which are $A$ and $B$ while the
third is $AB$. If the line joining $A$ and $B$ is tangent to the curve at some point $p$ then either this line intersects
$\mathscr{C}_f(\mathbb{R})$ in exactly two points, $p$ and some other point $p'$, or intersects the curve in only one
point $p$. If the line intersects $\mathscr{C}_f(\mathbb{R})$ in two points $p$ and $p'$, then either $p=A=B$ in which
case $AB=p'$, or $A\neq B$ in which case (irrespective of whether $p=A$ and $p'=B$ or vice-versa) one would have $p=AB$.
While if the line intersects $\mathscr{C}_f(\mathbb{R})$ in only one point $p$ then $p=A=B=AB$.

The above discussion establishes a binary operation on elliptic
curves that produces, for any two points $A$ and $B$ a uniquely
defined third point $AB$. This binary operation in turn produces, as
will be described next, another binary operation, denoted by $+$,
that defines a group structure on $\mathscr{C}_f(\mathbb{R})$ that
is associated with the straight-line construction discussed so far.

A group structure on an elliptic curve $\mathscr{C}_f(\mathbb{R})$ is defined as follows: Consider an arbitrary point,
denoted by $0$, on $\mathscr{C}_f(\mathbb{R})$. We define, for any two points $A$ and $B$ on $\mathscr{C}_f(\mathbb{R})$,
the point $A+B$ by
\begin{equation}
A+B=0(AB),
\end{equation}
meaning that we first determine the point $AB$ as above, then we determine the point $0(AB)$ corresponding to $0$ and $AB$. Irrespective of the choice of the
point $0$, one has the following theorem on a group structure determined by $+$ on $\mathscr{C}_f(\mathbb{R})$.

\begin{theorem}
Let $\mathscr{C}_f(\mathbb{R})$ be an elliptic curve, and let $0$ be any point on $\mathscr{C}_f(\mathbb{R})$.
Then the above binary operation $+$ defines an Abelian group structure on $\mathscr{C}_f(\mathbb{R})$, with $0$ being
the identity element and $-A=A(00)$ for every point $A$.
\end{theorem}

The proof is very lengthy and can be found in \cite{NMZ}. We first
note that if $0$ and $0'$ are two different points on an elliptic
curve with associated binary operations $+$ and $+'$, then one can
easily show that for any two points $A$ and $B$
\begin{equation}
A+'B=A+B-0'.
\end{equation}
This shows that the various group structures that can be defined on an elliptic curve by considering all possible
points $0$ and associated operations $+$, are essentially the same, up to a "translation".

\begin{lemma}
Consider the group structure on an elliptic curve
$\mathscr{C}_f(\mathbb{R})$, corresponding to an operation $+$ with
identity element $0$. If the cubic polynomial $f$ has rational
coefficients, then the subset
$\mathscr{C}_f(\mathbb{Q})\subset\mathscr{C}_f(\mathbb{R})$ of
rational solutions to $f(x,y)=0$ forms a subgroup of
$\mathscr{C}_f(\mathbb{R})$ if and only if $0$ is itself a rational
point (i.e. a rational solution).
\end{lemma}

\begin{proof}
If $\mathscr{C}_f(\mathbb{Q})$ is a subgroup of $\mathscr{C}_f(\mathbb{R})$, then it must contain the identity $0$,
and thus $0$ would be a rational point. Conversely, assume that $0$ is a rational point. First, since $f$ has rational
coefficients, then for any two rational points $A$ and $B$ in $\mathscr{C}_f(\mathbb{Q})$ one must have that $AB$ is
also rational, and thus (since $0$ is assumed rational) that $0(AB)$ is rational, making $A+B=0(AB)$ rational.
Thus $\mathscr{C}_f(\mathbb{Q})$ would be closed under $+$. Moreover, since for every $A\in\mathscr{C}_f(\mathbb{Q})$
one has that $-A=A(00)$, then $-A$ is also rational, which makes $\mathscr{C}_f(\mathbb{Q})$ closed under inversion.
Hence $\mathscr{C}_f(\mathbb{Q})$ is a subgroup.
\end{proof}

Thus by lemma 18, the set of all rational points on an elliptic curve form a subgroup of the group determined by
the curve and a point $0$, if and only if the identity element $0$ is itself a rational point. In other words,
one finds that if the elliptic curve $\mathscr{C}_f(\mathbb{R})$ contains one rational point $p$, then there exists
a group structure on $\mathscr{C}_f(\mathbb{R})$, with $0=p$ and the corresponding binary operation $+$, such that
the set $\mathscr{C}_f(\mathbb{Q})$ of all rational points on $\mathscr{C}_f(\mathbb{R})$ is a group.

One thing to note about rational solutions to general polynomial
functions $f(x,y)$, is that they correspond to integer solution to a
corresponding {\it homogeneous} polynomial $h(X,Y,Z)$ in three
variables, and vice-verse, where homogeneous practically means that
this function is a linear sum of terms each of which has the same
power when adding the powers of the variables involved in this term.
For example $XY^2-2X^3+XYZ+Z^3$ is homogeneous.

In fact a rational solution $x=a/b$ and $y=c/d$ for $f(x,y)=0$,
where $a,b,c,d$ are integers, can first be written as $x=ad/bd$ and
$y=cb/bd$, and thus one can always have this solution in the form
$x=X/Z$ and $y=Y/Z$, where $X=ad, Y=cb$ and $Z=bd$. If $x=X/Z$ and
$y=Y/Z$ are replaced in $f(x,y)=0$, one obtains a new version
$h(X,Y,Z)=0$ of this equation written in terms of the new variables
$X,Y,Z$. One can immediately see that this new polynomial function
$h(X,Y,Z)$ is homogeneous in $X,Y,Z$. The homogeneous function
$h(X,Y,Z)$ in $X,Y,Z$ is the form that $f(x,y)$ takes in projective
space, where in this case the transformations $x=X/Z$ and $y=Y/Z$
define the projective transformation that take $f(x,y)$ to
$h(X,Y,Z)$.

If we now go back to cubic equation $f(x,y)=0$, one can transform
this function into its cubic homogeneous form $h(X,Y,Z)=0$, where
\begin{eqnarray}
h(X,Y,Z)=aX^3&+&bX^2Y+cXY^2+dY^3+eX^2Z\nonumber\\&+&fXYZ+gY^2Z+hXZ^2+iYZ^2+jZ^3,
\end{eqnarray}
by using the projective transformation $x=X/Z$ and $y=Y/Z$. Then, by
imposing some conditions, such as requiring that the point $(1,0,0)$
(in projective space) satisfy this equation, and that the line
tangent to the curve at the point $(1,0,0)$ be the $Z$-axis that
intersects the curve in the point $(0,1,0)$, and that the $X$-axis
is the line tangent to the curve at $(0,1,0)$, then one can
immediately show that the homogeneous cubic equation above becomes
of the form
\begin{equation}
h(X,Y,Z)=cXY^2+eX^2Z+fXYZ+hXZ^2+iYZ^2+jZ^3.
\end{equation}
Which, by using the projective transformation again, and using new
coefficients, gives that points on the curve
$\mathscr{C}_f(\mathbb{R})$ are precisely those on the curve
$\mathscr{C}_h(\mathbb{R})$, where
\begin{equation}
h(x,y)=axy^2+bx^2+cxy+dx+ey+f.
\end{equation}
And with further simple change of variables (consisting of
polynomial functions in $x$ and $y$ with rational coefficients) one
obtains that the points on the curve $\mathscr{C}_f(\mathbb{R})$ are
precisely those on $\mathscr{C}_g(\mathbb{R})$ where
\begin{equation}
g(x,y)=y^2-4x^3+g_2x-g_3,
\end{equation}
i.e. that $\mathscr{C}_f(\mathbb{R})=\mathscr{C}_g(\mathbb{R})$. The
equation $g(x,y)=0$, where $g$ is given in (8.10), is said to be the
{\it Weierstrass normal form} of the equation $f(x,y)=0$. Thus, in
particular, any elliptic curve defined by a cubic $f$, is {\it
birationally equivalent} to an elliptic curve defined by a
polynomial $g(x,y)$ as above. Birational equivalence between curves
is defined here as being a rational transformation, together with
its inverse transformation, that takes the points on one curve to
another, and vice-versa.


\section{The Riemann Zeta Function}
\index{Riemann Zeta Function} The Riemann zeta function $\zeta(z)$
is an analytic function that is a very important function in
analytic number theory. It is (initially) defined in some domain in
the complex plane by the special type of Dirichlet series given by
\begin{equation}
\zeta(z)=\sum_{n=1}^{\infty}\frac{1}{n^z},
\end{equation}
where $Re(z)>1$. It can be readily verified that the given series
converges locally uniformly, and thus that $\zeta(z)$ is indeed
analytic in the domain in the complex plane $\bf C$ defined by
$Re(z)>1$, and that this function does not have a zero in this
domain.

We first prove the following result which is called the Euler
Product Formula.\index{Euler Product Formula}

\begin{theorem}
$\zeta(z)$, as defined by the series above, can be written in the form
\begin{equation}
\zeta(z)=\prod_{n=1}^{\infty}\frac{1}{\left(1-\frac{1}{p_n^z}\right)},
\end{equation}
where $\{p_n\}$ is the sequence of all prime numbers.
\end{theorem}

\begin{proof}
knowing that if $|x|<1$ then
\begin{equation}
\frac{1}{1-x}=\sum_{k=0}^{\infty}x^k,
\end{equation}
one finds that each term $\frac{1}{1-\frac{1}{p_n^z}}$ in $\zeta(z)$ is given by
\begin{equation}
\frac{1}{1-\frac{1}{p_n^z}}=\sum_{k=0}^{\infty}\frac{1}{p_n^{kz}},
\end{equation}
since every $|1/p_n^z|<1$ if $Re(z)>1$. This gives that for any integer $N$
\begin{eqnarray}
\prod_{n=1}^N\frac{1}{\left(1-\frac{1}{p_n^z}\right)}&=&\prod_{n=1}^N\left(1+
\frac{1}{p_n^z}+\frac{1}{p_n^{2z}}+\cdots\right)\nonumber\\&=&\sum\frac{1}{p_
{n_1}^{k_1z}\cdots p_{n_i}^{k_jz}}\\&=&\sum\frac{1}{n^z}\nonumber
\end{eqnarray}
where $i$ ranges over $1,\cdots,N$, and $j$ ranges from $0$ to
$\infty$, and thus the integers $n$ in the third line above range
over all integers whose prime number factorization consist of a
product of powers of the primes $p_1=2,\cdots, p_N$. Also note that
each such integer $n$ appears only once in the sum above.

Now since the series in the definition of $\zeta(z)$ converges
absolutely and the order of the terms in the sum does not matter for
the limit, and since, eventually, every integer $n$ appears on the
right hand side of 8.15 as $N\longrightarrow\infty$, then
$\lim_{N\to\infty}\left[\sum\frac{1}{n^z}\nonumber\right]_N=\zeta(z)$.
Moreover,
$\lim_{N\to\infty}\prod_{n=1}^N\frac{1}{\left(1-\frac{1}{p_n^z}\right)}$
exists, and the result follows.
\end{proof}

The Riemann zeta function $\zeta(z)$ as defined through the special
Dirichlet series above,  can be continued analytically to an
analytic function through out the complex plane {\bf C} except to
the point $z=1$, where the continued function has a pole of order 1.
Thus the continuation of $\zeta(z)$ produces a meromorphic function
in {\bf C} with a simple pole at 1. The following theorem gives this
result.

\begin{theorem}
$\zeta(z)$, as defined above, can be continued meromorphically in
{\bf C}, and can be written in the form
$\zeta(z)=\frac{1}{z-1}+f(z)$, where $f(z)$ is entire.
\end{theorem}

Given this continuation of $\zeta(z)$, and also given the functional
equation that is satisfied by this continued function, and which is
\begin{equation}
\zeta(z)=2^z\pi^{z-1}\sin\left(\frac{\pi z}{2}\right)\Gamma(1-z)\zeta(1-z),
\end{equation}
(see a proof in \cite{Apostol}), where $\Gamma$ is the complex gamma
function, one can deduce that the continued $\zeta(z)$ has zeros at
the points $z=-2,-4,-6,\cdots$ on the negative real axis. This
follows as such: The complex gamma function $\Gamma(z)$ has poles at
the points $z=-1,-2,-3,\cdots$ on the negative real line, and thus
$\Gamma(1-z)$ must have poles at $z=2,3,\cdots$ on the positive real
axis. And since $\zeta(z)$ is analytic at these points, then it must
be that either $\sin\left(\frac{\pi z}{2}\right)$ or $\zeta(1-z)$
must have zeros at the points $z=2,3,\cdots$ to cancel out the poles
of $\Gamma(1-z)$, and thus make $\zeta(z)$ analytic at these points.
And since $\sin\left(\frac{\pi z}{2}\right)$ has zeros at
$z=2,4,\cdots$, but not at $z=3,5,\cdots$, then it must be that
$\zeta(1-z)$ has zeros at $z=3,5,\cdots$. This gives that $\zeta(z)$
has zeros at $z=-2,-4,-6\cdots$.

It also follows from the above functional equation, and from the
above mentioned fact that $\zeta(z)$ has no zeros in the domain
where $Re(z)>1$, that these zeros at $z=-2,-4,-6\cdots$ of
$\zeta(z)$ are the only zeros that have real parts either less that
0, or greater than 1. \index{Riemann Hypothesis} It was conjectured
by Riemann, {\it The Riemann Hypothesis}, that every other zero of
$\zeta(z)$ in the remaining strip $0\leq Re(z)\leq 1$, all exist on
the vertical line $Re(z)=1/2$. This hypothesis was checked for zeros
in this strip with very large modulus, but remains without a general
proof. It is thought that the consequence of the Riemann hypothesis
on number theory, provided it turns out to be true, is immense.



% 1 z q a Q A Z



\cleardoublepage
\phantomsection
\hypertarget{TOC}{}
\pdfbookmark[0]{Bibliography}{TOC}
\begin{thebibliography}{99}
\bibitem{Andrews} George E. Andrews, \textit{Number Theory}, Dover, New
York, 1994.\\
\bibitem{Andrews}George E. Andrews, \textit{The Theory of Partitions}. Reprint of the 1976 original.,
Cambridge Mathematical Library. Cambridge University Press,
Cambridge, 1998\\
\bibitem{Apostol} Tom M. Apostol, \textit{Introduction to Analytic Number
Theory}.  Springer, New York, 1976.\\
\bibitem{Baker} A. Baker, \textit{Transcendantal Number Theory},
Cambridge University Press (London), 1975.\\
\bibitem{Cassels} J.W.S. Cassels, \textit{An introduction to the Geometry of
Numbers}, Springer-Verlag (Berlin), 1971.\\
\bibitem{Davenprot2} H. Davenport, \textit{Multiplicative Number
Theory}, 2nd edition, Springer-Verlag (New York), 1980.\\
\bibitem{Davenport} H. Davenport, \textit{The higher Arithmetic:  an
introduction to the Theory of Numbers}, 7th edition, Cambridge
University Press 1999.\\
\bibitem{Edwards} H.M. Edwards, \textit{Riemann's Zeta Function}, Dover,
New York, 2001.\\
\bibitem{Grosswald} E. Grosswald, \textit{Topics from the Theory of
Numbers}. New York: The Macmillan Co. (1966).\\
\bibitem{HR} G.H. Hardy and E.M. Wright, \textit{An Introduction to the
Theory of Numbers}, 5th ed. Oxford University Press, Oxford,
1979.\\
\bibitem{Ireland} K.F. Ireland and M. Rosen, \textit{A Classical Introduction to Modern Number
Theory}, Springer-Verlag (New York), 1982.\\
\bibitem{Khinchin} A. Ya. Khinchin,
 \textit{Continued fractions}.
With a preface by B. V. Gnedenko. Translated from the third (1961)
Russian edition. Reprint of the 1964 translation.
Dover Publications, Inc., Mineola, NY, 1997.\\
\bibitem{Knopp} M.I. Knopp, \textit{Modular Functions in Analytic Number
Theory},  Markham, Chicago 1970. \\
\bibitem{Landau} E. Landau, \textit{Elementary Number Theory},
Chelsea (New York), 1958.\\
\bibitem{Leveque1} W.J. Leveque, \textit{Elementary Theory of
Numbers}, Dover, New York, 1990.\\
\bibitem{Leveque} W.J. Leveque, \textit{Fundamentals of Number
Theory}, Dover, New York, 1996.\\
\bibitem{Nagell} T. Nagell, \textit{Introduction to Number Theory},
Chelsea (New York), 1981.\\
\bibitem{NMZ} I. Niven, H.L. Montgomery and H.S. Zuckerman, \textit{An
Introduction to the Theory of Numbers}, 5th edition, John Wiley
and Sons 1991.\\
\bibitem{Poorten} A. J. Van der Poorten,
\textit{Continued fraction expansions of values of the exponential
function and related fun with continued fractions},
 Nieuw Arch. Wisk. (4) 14 (1996), no. 2, 221--230.\\
 \bibitem{Rademacher} H. Rademacher, \textit{Lectures on Elementary Number
 Theory}. Krieger, 1977.\\
\bibitem{Rosen} Kenneth H. Rosen, \textit{Elementary Number Theory and its
Applications}.  Fifth Edition. Pearson, Addison Wesley, USA,
2005.\\
\end{thebibliography}


\cleardoublepage
\phantomsection
\pdfbookmark[0]{Index}{Index}
\printindex
\end{document}