1 
%$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_pri0/c_pri0.tex,v 1.6 2003/11/30 01:18:17 dtashley Exp $ 
%$Header$ 
2 


3 
\chapter[\cprizeroshorttitle{}]{\cprizerolongtitle{}} 
\chapter[\cprizeroshorttitle{}]{\cprizerolongtitle{}} 
4 


5 
\label{cpri0} 
\label{cpri0} 
6 


7 
\beginchapterquote{``The number of primes less than 1,000,000,000 is 
\beginchapterquote{``The number of primes less than 1,000,000,000 is 
8 
50,847,478: this is enough for an engineer, and he 
50,847,478: this is enough for an engineer, and he 
9 
can be perfectly happy without the rest.''} 
can be perfectly happy without the rest.''} 
10 
{G.H. Hardy \cite{bibref:b:mathematiciansapology:1940}, p. 102} 
{G.H. Hardy \cite{bibref:b:mathematiciansapology:1940}, p. 102} 
11 


12 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
13 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
14 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
15 
\section{Introduction} 
\section{Introduction} 
16 
%Section Tag INT0 
%Section Tag INT0 
17 
\label{cpri0:int0} 
\label{cpri0:int0} 
18 


19 
This chapter presents important properties of integers and prime numbers; and 
This chapter presents important properties of integers and prime numbers; and 
20 
related topics and concepts. Nearly all of the ideas presented come from 
related topics and concepts. Nearly all of the ideas presented come from 
21 
number theory (a branch of mathematics). 
number theory (a branch of mathematics). 
22 


23 
Our aim in this chapter is to provide the reader 
Our aim in this chapter is to provide the reader 
24 
with the background necessary to understand other 
with the background necessary to understand other 
25 
topics in the work (Farey series, 
topics in the work (Farey series, 
26 
continued fractions, and rational approximation). 
continued fractions, and rational approximation). 
27 
Because this work is concerned with microcontroller 
Because this work is concerned with microcontroller 
28 
software development (rather than mathematics), 
software development (rather than mathematics), 
29 
the treatment is regrettably minimal. 
the treatment is regrettably minimal. 
30 


31 


32 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
33 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
34 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
35 
\section{Sets Of Integers} 
\section{Sets Of Integers} 
36 
%Section tag: SOI0 
%Section tag: SOI0 
37 
\label{cpri0:soi0} 
\label{cpri0:soi0} 
38 


39 
An\index{integer}\index{sets of integers}\index{integer!sets of} 
An\index{integer}\index{sets of integers}\index{integer!sets of} 
40 
\emph{integer} is a positive or negative whole number, such as 0, 
\emph{integer} is a positive or negative whole number, such as 0, 
41 
$\pm$1, $\pm$2, $\pm$3, \ldots{} (\cite{bibref:b:penguindictionaryofmathematics:2ded}). 
$\pm$1, $\pm$2, $\pm$3, \ldots{} (\cite{bibref:b:penguindictionaryofmathematics:2ded}). 
42 
The set of integers is denoted $\vworkintset$:\index{Z@$\vworkintset$}% 
The set of integers is denoted $\vworkintset$:\index{Z@$\vworkintset$}% 
43 
\index{integer!Z@$\vworkintset$} 
\index{integer!Z@$\vworkintset$} 
44 


45 
\begin{equation} 
\begin{equation} 
46 
\vworkintset = \{ \ldots{} , 3, 2, 1, 0, 1, 2, 3, \ldots{} \}. 
\vworkintset = \{ \ldots{} , 3, 2, 1, 0, 1, 2, 3, \ldots{} \}. 
47 
\end{equation} 
\end{equation} 
48 


49 
A \emph{natural number}\index{natural number}\index{counting number} 
A \emph{natural number}\index{natural number}\index{counting number} 
50 
\index{integer!natural number}\index{integer!counting number} (or \emph{counting number}) 
\index{integer!natural number}\index{integer!counting number} (or \emph{counting number}) 
51 
is a positive integer, 
is a positive integer, 
52 
such as 1, 2, 3, \ldots{} (\cite{bibref:b:penguindictionaryofmathematics:2ded}). 
such as 1, 2, 3, \ldots{} (\cite{bibref:b:penguindictionaryofmathematics:2ded}). 
53 
In this work, the set of natural numbers is denoted 
In this work, the set of natural numbers is denoted 
54 
$\vworkintsetpos$:\index{N@$\vworkintsetpos$}\index{integer!N@$\vworkintsetpos$} 
$\vworkintsetpos$:\index{N@$\vworkintsetpos$}\index{integer!N@$\vworkintsetpos$} 
55 


56 
\begin{equation} 
\begin{equation} 
57 
\vworkintsetpos = \{ 1, 2, 3, 4, 5, \ldots{} \}. 
\vworkintsetpos = \{ 1, 2, 3, 4, 5, \ldots{} \}. 
58 
\end{equation} 
\end{equation} 
59 


60 
A \emph{nonnegative integer}\index{nonnegative integer}\index{integer!nonnegative} 
A \emph{nonnegative integer}\index{nonnegative integer}\index{integer!nonnegative} 
61 
is an integer which is not negative, 
is an integer which is not negative, 
62 
such as 0, 1, 2, 3, \ldots{}. In this work, the set of nonnegative 
such as 0, 1, 2, 3, \ldots{}. In this work, the set of nonnegative 
63 
integers is denoted $\vworkintsetnonneg$:\footnote{This notation is 
integers is denoted $\vworkintsetnonneg$:\footnote{This notation is 
64 
somewhat unconventional, as in most works $\vworkintsetnonneg$ denotes 
somewhat unconventional, as in most works $\vworkintsetnonneg$ denotes 
65 
the set of natural numbers; see \cite{bibref:b:penguindictionaryofmathematics:2ded}, 
the set of natural numbers; see \cite{bibref:b:penguindictionaryofmathematics:2ded}, 
66 
p. 223.}\index{Z+@$\vworkintsetnonneg$}\index{integer!Z+@$\vworkintsetnonneg$} 
p. 223.}\index{Z+@$\vworkintsetnonneg$}\index{integer!Z+@$\vworkintsetnonneg$} 
67 


68 
\begin{equation} 
\begin{equation} 
69 
\vworkintsetnonneg = \{ 0, 1, 2, 3, 4, \ldots{} \}. 
\vworkintsetnonneg = \{ 0, 1, 2, 3, 4, \ldots{} \}. 
70 
\end{equation} 
\end{equation} 
71 


72 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
73 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
74 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
75 
\section{Divisibility Of Integers With No Remainder} 
\section{Divisibility Of Integers With No Remainder} 
76 
\label{cpri0:doi0} 
\label{cpri0:doi0} 
77 


78 
We follow the convention of \cite{bibref:b:HardyAndWrightClassic} 
We follow the convention of \cite{bibref:b:HardyAndWrightClassic} 
79 
and use `$\vworkdivides$' 
and use `$\vworkdivides$' 
80 
\index{divides@divides ($\vworkdivides$)} 
\index{divides@divides ($\vworkdivides$)} 
81 
\index{@$\vworkdivides$ (divides)} 
\index{@$\vworkdivides$ (divides)} 
82 
to denote that one integer can divide 
to denote that one integer can divide 
83 
another with no remainder, and use `$\vworknotdivides$' 
another with no remainder, and use `$\vworknotdivides$' 
84 
\index{divides@divides ($\vworkdivides$)} 
\index{divides@divides ($\vworkdivides$)} 
85 
\index{@$\vworknotdivides$ (doesn't divide)} 
\index{@$\vworknotdivides$ (doesn't divide)} 
86 
to denote 
to denote 
87 
that one integer cannot divide another without a 
that one integer cannot divide another without a 
88 
remainder. $a \vworkdivides b$, read ``$a$ 
remainder. $a \vworkdivides b$, read ``$a$ 
89 
divides $b$'', denotes that $b/a$ has no remainder; and 
divides $b$'', denotes that $b/a$ has no remainder; and 
90 
$a \vworknotdivides b$, read ``$a$ does not divide $b$'', denotes 
$a \vworknotdivides b$, read ``$a$ does not divide $b$'', denotes 
91 
that $b/a$ has a remainder. 
that $b/a$ has a remainder. 
92 


93 
The following implications (\cite{bibref:b:HardyAndWrightClassic}, p. 1) 
The following implications (\cite{bibref:b:HardyAndWrightClassic}, p. 1) 
94 
are intuitively plain, and we accept them without proof. 
are intuitively plain, and we accept them without proof. 
95 


96 
\begin{equation} 
\begin{equation} 
97 
b \vworkdivides a \wedge c \vworkdivides b \vworkhimp c \vworkdivides a 
b \vworkdivides a \wedge c \vworkdivides b \vworkhimp c \vworkdivides a 
98 
\end{equation} 
\end{equation} 
99 


100 
\begin{equation} 
\begin{equation} 
101 
b \vworkdivides a \vworkhimp b c \vworkdivides a c 
b \vworkdivides a \vworkhimp b c \vworkdivides a c 
102 
\end{equation} 
\end{equation} 
103 


104 
\begin{equation} 
\begin{equation} 
105 
c \vworkdivides a \wedge c \vworkdivides b \vworkhimp c \vworkdivides (m a + n b) 
c \vworkdivides a \wedge c \vworkdivides b \vworkhimp c \vworkdivides (m a + n b) 
106 
\end{equation} 
\end{equation} 
107 


108 


109 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
110 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
111 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
112 
\section{Prime Numbers And Composite Numbers} 
\section{Prime Numbers And Composite Numbers} 
113 
%Section tag: PNC0 
%Section tag: PNC0 
114 
\label{cpri0:pnc0} 
\label{cpri0:pnc0} 
115 


116 
A \emph{prime number}\index{prime number} (or, more tersely, a \emph{prime}) 
A \emph{prime number}\index{prime number} (or, more tersely, a \emph{prime}) 
117 
is a natural number 
is a natural number 
118 
which has as its naturalnumber factors only 1 and itself. 
which has as its naturalnumber factors only 1 and itself. 
119 
Any natural number which is not a prime is a product of primes, and is called 
Any natural number which is not a prime is a product of primes, and is called 
120 
a \emph{composite number}\index{composite number} (or just a \emph{composite}). 
a \emph{composite number}\index{composite number} (or just a \emph{composite}). 
121 
The number `1' is considered neither prime nor composite. 
The number `1' is considered neither prime nor composite. 
122 


123 
As examples, the first ten prime numbers are 2, 3, 5, 7, 11, 
As examples, the first ten prime numbers are 2, 3, 5, 7, 11, 
124 
13, 17, 19, 23, and 29. The first ten composite numbers are 
13, 17, 19, 23, and 29. The first ten composite numbers are 
125 
$4 = 2 \times 2$, 
$4 = 2 \times 2$, 
126 
$6 = 2 \times 3$, 
$6 = 2 \times 3$, 
127 
$8 = 2 \times 2 \times 2$, 
$8 = 2 \times 2 \times 2$, 
128 
$9 = 3 \times 3$, 
$9 = 3 \times 3$, 
129 
$10 = 2 \times 5$, 
$10 = 2 \times 5$, 
130 
$12 = 2 \times 2 \times 3$, 
$12 = 2 \times 2 \times 3$, 
131 
$14 = 2 \times 7$, 
$14 = 2 \times 7$, 
132 
$15 = 3 \times 5$, 
$15 = 3 \times 5$, 
133 
$16 = 2 \times 2 \times 2 \times 2$, 
$16 = 2 \times 2 \times 2 \times 2$, 
134 
and $18 = 2 \times 3 \times 3$. 
and $18 = 2 \times 3 \times 3$. 
135 


136 
Many properties of prime numbers were understood even prior 
Many properties of prime numbers were understood even prior 
137 
to Euclid's time\footnote{Euclid's \emph{gcd($\cdot{},\cdot{}$)} algorithm, for example, 
to Euclid's time\footnote{Euclid's \emph{gcd($\cdot{},\cdot{}$)} algorithm, for example, 
138 
dates back to at least 200 B.C.} ($\approx$200 B.C.), but many other properties 
dates back to at least 200 B.C.} ($\approx$200 B.C.), but many other properties 
139 
were discovered relatively recently (1600 A.D. and later). In recent history, 
were discovered relatively recently (1600 A.D. and later). In recent history, 
140 
the difficulty of factoring large composite numbers into their [large] prime 
the difficulty of factoring large composite numbers into their [large] prime 
141 
components has become a linchpin of cryptography. 
components has become a linchpin of cryptography. 
142 


143 


144 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
145 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
146 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
147 
\section{Properties Of Prime Numbers} 
\section{Properties Of Prime Numbers} 
148 
%Subsection Tag: PPN0 
%Subsection Tag: PPN0 
149 
\label{cpri0:ppn0} 
\label{cpri0:ppn0} 
150 


151 
This section presents several important properties of prime numbers. Most 
This section presents several important properties of prime numbers. Most 
152 
of our readerspresumably being in predominantly technical vocationsare 
of our readerspresumably being in predominantly technical vocationsare 
153 
probably familiar with most of these properties. 
probably familiar with most of these properties. 
154 


155 
Prime numbers are the fundamental currency of arithmeticthe fundamental 
Prime numbers are the fundamental currency of arithmeticthe fundamental 
156 
atomic ``stuff'' from which all integers are constructed. The first properties 
atomic ``stuff'' from which all integers are constructed. The first properties 
157 
presented involve this aspect of primes. The presentation and the 
presented involve this aspect of primes. The presentation and the 
158 
presentation order in 
presentation order in 
159 
\cite{bibref:b:HardyAndWrightClassic} is perfect, so we don't deviate. 
\cite{bibref:b:HardyAndWrightClassic} is perfect, so we don't deviate. 
160 


161 
\begin{vworktheoremstatement} 
\begin{vworktheoremstatement} 
162 
\label{thm:cpri0:ppn0:00} 
\label{thm:cpri0:ppn0:00} 
163 
Every positive integer, except 1, is a product of primes. 
Every positive integer, except 1, is a product of primes. 
164 
\end{vworktheoremstatement} 
\end{vworktheoremstatement} 
165 
\begin{vworktheoremproof} 
\begin{vworktheoremproof} 
166 
See \cite{bibref:b:HardyAndWrightClassic}, p. 2. 
See \cite{bibref:b:HardyAndWrightClassic}, p. 2. 
167 
\end{vworktheoremproof} 
\end{vworktheoremproof} 
168 
\vworktheoremfooter{} 
\vworktheoremfooter{} 
169 


170 
When a number is factored into its prime components, we 
When a number is factored into its prime components, we 
171 
follow \cite{bibref:b:HardyAndWrightClassic}, p. 2 in defining 
follow \cite{bibref:b:HardyAndWrightClassic}, p. 2 in defining 
172 
a standard (or canonical) form for such a factorization. 
a standard (or canonical) form for such a factorization. 
173 


174 
Theorem \ref{thm:cpri0:ppn0:00} establishes that any integer, except 1, can be factored 
Theorem \ref{thm:cpri0:ppn0:00} establishes that any integer, except 1, can be factored 
175 
into prime components. Theorem \ref{thm:cpri0:ppn0:01} (The Fundamental Theorem Of 
into prime components. Theorem \ref{thm:cpri0:ppn0:01} (The Fundamental Theorem Of 
176 
Arithmetic), establishes a stronger resultthat such a factorization 
Arithmetic), establishes a stronger resultthat such a factorization 
177 
is unique. 
is unique. 
178 


179 
\begin{equation} 
\begin{equation} 
180 
n = p_1^{a_1} p_2^{a_2} \ldots{} p_k^{a_k}; \; 
n = p_1^{a_1} p_2^{a_2} \ldots{} p_k^{a_k}; \; 
181 
(a_1 > 0, a_2 > 0, \ldots{} , a_k > 0, p_1 < p_2 < \ldots{} < p_k) 
(a_1 > 0, a_2 > 0, \ldots{} , a_k > 0, p_1 < p_2 < \ldots{} < p_k) 
182 
\end{equation} 
\end{equation} 
183 


184 
\begin{vworktheoremstatementpar}{The Fundamental Theorem Of Arithmetic} 
\begin{vworktheoremstatementpar}{The Fundamental Theorem Of Arithmetic} 
185 
\label{thm:cpri0:ppn0:01} 
\label{thm:cpri0:ppn0:01} 
186 
(\cite{bibref:b:HardyAndWrightClassic}, p. 3) The standard form of 
(\cite{bibref:b:HardyAndWrightClassic}, p. 3) The standard form of 
187 
$n$ is unique; apart from the rearrangement of factors, $n$ can be 
$n$ is unique; apart from the rearrangement of factors, $n$ can be 
188 
expressed as a product of primes in one way only. 
expressed as a product of primes in one way only. 
189 
\end{vworktheoremstatementpar} 
\end{vworktheoremstatementpar} 
190 
\begin{vworktheoremproof} 
\begin{vworktheoremproof} 
191 
See \cite{bibref:b:HardyAndWrightClassic}, p. 21. 
See \cite{bibref:b:HardyAndWrightClassic}, p. 21. 
192 
\end{vworktheoremproof} 
\end{vworktheoremproof} 
193 
\vworktheoremfooter{} 
\vworktheoremfooter{} 
194 


195 
A \index{prime number!properties} reasonable question to ask is, is there a largest prime number? 
A \index{prime number!properties} reasonable question to ask is, is there a largest prime number? 
196 
Or, equivalently, is there a limited supply of prime numbers? It is known 
Or, equivalently, is there a limited supply of prime numbers? It is known 
197 
that there is no largest prime number and that there is an infinite number 
that there is no largest prime number and that there is an infinite number 
198 
of prime numbers. 
of prime numbers. 
199 
Euclid's famous proof that there is no largest prime number is reproduced below. 
Euclid's famous proof that there is no largest prime number is reproduced below. 
200 


201 
\begin{vworktheoremstatementpar}{Euclid's Second Theorem} 
\begin{vworktheoremstatementpar}{Euclid's Second Theorem} 
202 
The number of primes is infinite.\index{Euclid}\index{Euclid!Second Theorem}% 
The number of primes is infinite.\index{Euclid}\index{Euclid!Second Theorem}% 
203 
\index{prime number!no largest prime number} 
\index{prime number!no largest prime number} 
204 
\end{vworktheoremstatementpar} 
\end{vworktheoremstatementpar} 
205 
\begin{vworktheoremproof} 
\begin{vworktheoremproof} 
206 
(\cite{bibref:b:HardyAndWrightClassic}, p.12) Assume there is a largest 
(\cite{bibref:b:HardyAndWrightClassic}, p.12) Assume there is a largest 
207 
prime number, denoted $p$. Let 
prime number, denoted $p$. Let 
208 
$2 \times 3 \times 5 \times \ldots \times p$ be the aggregate (i.e. product) 
$2 \times 3 \times 5 \times \ldots \times p$ be the aggregate (i.e. product) 
209 
of primes up to $p$, and let 
of primes up to $p$, and let 
210 


211 
\begin{equation} 
\begin{equation} 
212 
q = (2 \times 3 \times 5 \times \ldots{} \times p) + 1. 
q = (2 \times 3 \times 5 \times \ldots{} \times p) + 1. 
213 
\end{equation} 
\end{equation} 
214 


215 
$q$ is not divisible by any of the prime numbers $2, 3, 5, \ldots{}, p$. $q$ 
$q$ is not divisible by any of the prime numbers $2, 3, 5, \ldots{}, p$. $q$ 
216 
is therefore either prime, or divisible by a prime between $p$ and $q$. In 
is therefore either prime, or divisible by a prime between $p$ and $q$. In 
217 
either case there is a prime greater than $p$, which is a contradiction, and 
either case there is a prime greater than $p$, which is a contradiction, and 
218 
proves the theorem. 
proves the theorem. 
219 
\end{vworktheoremproof} 
\end{vworktheoremproof} 
220 
%\vworktheoremfooter{} 
%\vworktheoremfooter{} 
221 


222 
\begin{vworktheoremstatementpar}{Euclid's First Theorem} 
\begin{vworktheoremstatementpar}{Euclid's First Theorem} 
223 
\index{Euclid}\index{Euclid!First Theorem}% 
\index{Euclid}\index{Euclid!First Theorem}% 
224 
If $p$ is prime and $p \vworkdivides{} a b$, then $p \vworkdivides{} a$ 
If $p$ is prime and $p \vworkdivides{} a b$, then $p \vworkdivides{} a$ 
225 
or $p \vworkdivides{} b$. 
or $p \vworkdivides{} b$. 
226 
\end{vworktheoremstatementpar} 
\end{vworktheoremstatementpar} 
227 
\begin{vworktheoremproof} 
\begin{vworktheoremproof} 
228 
Waiting on information for the proof. 
Waiting on information for the proof. 
229 
\end{vworktheoremproof} 
\end{vworktheoremproof} 
230 
\begin{vworktheoremparsection}{Remarks} 
\begin{vworktheoremparsection}{Remarks} 
231 
\begin{itemize} 
\begin{itemize} 
232 
\item $p$ may divide both $a$ and $b$: ``or'' is used in the \emph{logical} sense. 
\item $p$ may divide both $a$ and $b$: ``or'' is used in the \emph{logical} sense. 
233 
\item This theorem essentially says that the divisibility by a prime may 
\item This theorem essentially says that the divisibility by a prime may 
234 
not be ``split'' across the two factors $a$ and $b$ so as to obscure 
not be ``split'' across the two factors $a$ and $b$ so as to obscure 
235 
it; i.e. primes are the fundamental currency of arithmetic. 
it; i.e. primes are the fundamental currency of arithmetic. 
236 
\item Note that this statement is not true in general for a composite $p$. 
\item Note that this statement is not true in general for a composite $p$. 
237 
For example, let $p = 6$, $a = 10$, $b = 21$: $6 \vworkdivides{} 210$, 
For example, let $p = 6$, $a = 10$, $b = 21$: $6 \vworkdivides{} 210$, 
238 
but $6 \vworknotdivides{} 10$ and $6 \vworknotdivides{} 21$. 
but $6 \vworknotdivides{} 10$ and $6 \vworknotdivides{} 21$. 
239 


240 
\end{itemize} 
\end{itemize} 
241 
\end{vworktheoremparsection} 
\end{vworktheoremparsection} 
242 
%\vworktheoremfooter{} 
%\vworktheoremfooter{} 
243 


244 
\begin{vworklemmastatement} 
\begin{vworklemmastatement} 
245 
\label{lem:cpri0:ppn0:000p} 
\label{lem:cpri0:ppn0:000p} 
246 
For $a, b, x, y \in \vworkintsetpos$, if 
For $a, b, x, y \in \vworkintsetpos$, if 
247 


248 
\begin{equation} 
\begin{equation} 
249 
ax  by = 1 , 
ax  by = 1 , 
250 
\end{equation} 
\end{equation} 
251 


252 
then $a$ and $b$ are coprime. 
then $a$ and $b$ are coprime. 
253 
\end{vworklemmastatement} 
\end{vworklemmastatement} 
254 
\begin{vworklemmaproof} 
\begin{vworklemmaproof} 
255 
Assume that $a$ and $b$ are \emph{not} coprime, 
Assume that $a$ and $b$ are \emph{not} coprime, 
256 
i.e. that $\gcd(a,b) > 1$. Then 
i.e. that $\gcd(a,b) > 1$. Then 
257 


258 
\begin{equation} 
\begin{equation} 
259 
axby = 
axby = 
260 
\gcd(a,b) \left( { \frac{ax}{\gcd(a,b)}\frac{by}{\gcd(a,b)}} \right) 
\gcd(a,b) \left( { \frac{ax}{\gcd(a,b)}\frac{by}{\gcd(a,b)}} \right) 
261 
\neq 1 , 
\neq 1 , 
262 
\end{equation} 
\end{equation} 
263 


264 
since $\gcd(a,b) > 1$. 
since $\gcd(a,b) > 1$. 
265 
\end{vworklemmaproof} 
\end{vworklemmaproof} 
266 
%\vworklemmafooter{} 
%\vworklemmafooter{} 
267 


268 
\begin{vworklemmastatement} 
\begin{vworklemmastatement} 
269 
\label{lem:cpri0:ppn0:00a} 
\label{lem:cpri0:ppn0:00a} 
270 
The equation 
The equation 
271 


272 
\begin{equation} 
\begin{equation} 
273 
ax + by = n 
ax + by = n 
274 
\end{equation} 
\end{equation} 
275 


276 
(with $a,b \in \vworkintsetpos$) is soluble in integers 
(with $a,b \in \vworkintsetpos$) is soluble in integers 
277 
$x,y \in \vworkintset$ for any $n \in \vworkintset$ iff 
$x,y \in \vworkintset$ for any $n \in \vworkintset$ iff 
278 
$a$ and $b$ are coprime. 
$a$ and $b$ are coprime. 
279 
\end{vworklemmastatement} 
\end{vworklemmastatement} 
280 
\begin{vworklemmaproof} 
\begin{vworklemmaproof} 
281 
First, it will be shown that if $a$ and $b$ are coprime, 
First, it will be shown that if $a$ and $b$ are coprime, 
282 
any $n$ can be reached through some choice of 
any $n$ can be reached through some choice of 
283 
$x,y \in \vworkintset$. (In fact, we give a 
$x,y \in \vworkintset$. (In fact, we give a 
284 
procedure for choosing $x$ and $y$.) 
procedure for choosing $x$ and $y$.) 
285 


286 
Form the set 
Form the set 
287 


288 
\begin{equation} 
\begin{equation} 
289 
\label{eq:cpri0:ppn0:00a00} 
\label{eq:cpri0:ppn0:00a00} 
290 
\{ 0b \; mod \; a, 1b \; mod \; a, 2b \; mod \; a, 
\{ 0b \; mod \; a, 1b \; mod \; a, 2b \; mod \; a, 
291 
\ldots{} , (a2)b \; mod \; a, (a1)b \; mod \; a \} . 
\ldots{} , (a2)b \; mod \; a, (a1)b \; mod \; a \} . 
292 
\end{equation} 
\end{equation} 
293 


294 
Note in this set that each integer $\{0, \ldots, a1 \}$ 
Note in this set that each integer $\{0, \ldots, a1 \}$ 
295 
is present exactly once, but not necessarily in order. 
is present exactly once, but not necessarily in order. 
296 
To show that each integer 
To show that each integer 
297 
$\{0, \ldots, a1 \}$ is present exactly once, note that 
$\{0, \ldots, a1 \}$ is present exactly once, note that 
298 
the set contains exactly $a$ elements, and note that each 
the set contains exactly $a$ elements, and note that each 
299 
element is $\in \{0, \ldots, a1 \}$. In order for each 
element is $\in \{0, \ldots, a1 \}$. In order for each 
300 
integer $\{0, \ldots, a1 \}$ \emph{not} to be present 
integer $\{0, \ldots, a1 \}$ \emph{not} to be present 
301 
exactly once, the set must contain at least one duplication 
exactly once, the set must contain at least one duplication 
302 
of an element. Assume that a duplication exists, namely 
of an element. Assume that a duplication exists, namely 
303 
that $pb \; mod \; a = qb \; mod \; a$, for some $p$ and $q$ 
that $pb \; mod \; a = qb \; mod \; a$, for some $p$ and $q$ 
304 
with $p \neq q$ and $0 \leq p,q \leq a1$. In that case, 
with $p \neq q$ and $0 \leq p,q \leq a1$. In that case, 
305 
we would have $(qp) b = ka$. Because $a$ and $b$ are 
we would have $(qp) b = ka$. Because $a$ and $b$ are 
306 
coprime (share no prime factors), this would require $(qp)$ 
coprime (share no prime factors), this would require $(qp)$ 
307 
to have at least every prime factor in $a$ with at least the 
to have at least every prime factor in $a$ with at least the 
308 
same multiplicity as $a$, which would imply that 
same multiplicity as $a$, which would imply that 
309 
$(qp) \geq a$, a contradiction. Thus, there are no 
$(qp) \geq a$, a contradiction. Thus, there are no 
310 
duplicates in the set (\ref{eq:cpri0:ppn0:00a00}), and 
duplicates in the set (\ref{eq:cpri0:ppn0:00a00}), and 
311 
every integer $\{0, \ldots, a1 \}$ is present. 
every integer $\{0, \ldots, a1 \}$ is present. 
312 


313 
It is clear then that $x$ and $y$ can always be chosen by 
It is clear then that $x$ and $y$ can always be chosen by 
314 
``modulo shopping''. We could, for example, 
``modulo shopping''. We could, for example, 
315 
calculate $n \; mod \; a$, and find some $y$ 
calculate $n \; mod \; a$, and find some $y$ 
316 
s.t. $yb \; mod \; a = n \; mod \; a$, then choose $x$.\footnote{It 
s.t. $yb \; mod \; a = n \; mod \; a$, then choose $x$.\footnote{It 
317 
is guaranteed 
is guaranteed 
318 
that we \emph{can} find such an $x$ because 
that we \emph{can} find such an $x$ because 
319 
the choice of $x$ moves $n$ in steps 
the choice of $x$ moves $n$ in steps 
320 
of $a$thus by varying $x$ we can adjust $n$ to be \emph{any} 
of $a$thus by varying $x$ we can adjust $n$ to be \emph{any} 
321 
integer s.t. $n \; mod \; a = yb \; mod \; a$, and this means 
integer s.t. $n \; mod \; a = yb \; mod \; a$, and this means 
322 
that there is necessarily a choice for $x$ s.t. $ax+by=n$.} 
that there is necessarily a choice for $x$ s.t. $ax+by=n$.} 
323 
This technique is illustrated in Example \ref{ex:cpri0:ppn0:01}. 
This technique is illustrated in Example \ref{ex:cpri0:ppn0:01}. 
324 


325 
If $a$ and $b$ are not coprime, this is equivalent to the 
If $a$ and $b$ are not coprime, this is equivalent to the 
326 
statement that $\gcd(a,b) > 1$. The same argument as is present 
statement that $\gcd(a,b) > 1$. The same argument as is present 
327 
in Theorem \ref{thm:cpri0:ppn0:00a} 
in Theorem \ref{thm:cpri0:ppn0:00a} 
328 
and Equation \ref{eq:cpri0:ppn0:00a1} applyonly 
and Equation \ref{eq:cpri0:ppn0:00a1} applyonly 
329 
$n$ which are multiples of $\gcd(a,b)$ can be 
$n$ which are multiples of $\gcd(a,b)$ can be 
330 
``reached'', no matter what $x$ and $y$ are chosen. 
``reached'', no matter what $x$ and $y$ are chosen. 
331 
\end{vworklemmaproof} 
\end{vworklemmaproof} 
332 
%\vworklemmafooter{} 
%\vworklemmafooter{} 
333 


334 
\begin{vworkexamplestatement} 
\begin{vworkexamplestatement} 
335 
\label{ex:cpri0:ppn0:01} 
\label{ex:cpri0:ppn0:01} 
336 
Find integers $x$ and $y$ such that 
Find integers $x$ and $y$ such that 
337 


338 
\begin{equation} 
\begin{equation} 
339 
6 x + 77 y = 731 
6 x + 77 y = 731 
340 
\end{equation} 
\end{equation} 
341 
\end{vworkexamplestatement} 
\end{vworkexamplestatement} 
342 
\begin{vworkexampleparsection}{Solution I (``Modulo Shopping'')} 
\begin{vworkexampleparsection}{Solution I (``Modulo Shopping'')} 
343 
First, fix $y$ using the ``modulo shopping'' method 
First, fix $y$ using the ``modulo shopping'' method 
344 
suggested by Lemma \ref{lem:cpri0:ppn0:00a}. Building 
suggested by Lemma \ref{lem:cpri0:ppn0:00a}. Building 
345 
the set 
the set 
346 


347 
\begin{equation} 
\begin{equation} 
348 
\{ 0 \; mod \; 6, 77 \; mod \; 6, 154 \; mod \; 6, 
\{ 0 \; mod \; 6, 77 \; mod \; 6, 154 \; mod \; 6, 
349 
231 \; mod \; 6, 308 \; mod \; 6, 385 \; mod \; 6 \} 
231 \; mod \; 6, 308 \; mod \; 6, 385 \; mod \; 6 \} 
350 
\end{equation} 
\end{equation} 
351 


352 
yields $\{ 0, 5, 4, 3, 2, 1 \}$. Note that $731 \; mod \; 6$ 
yields $\{ 0, 5, 4, 3, 2, 1 \}$. Note that $731 \; mod \; 6$ 
353 
is 5, so we want to choose $y=1$ (corresponding to the second 
is 5, so we want to choose $y=1$ (corresponding to the second 
354 
element in the sets above). With $y$ fixed at 1, any choice 
element in the sets above). With $y$ fixed at 1, any choice 
355 
of $x$ will yield a result $6x + 77y$ such that 
of $x$ will yield a result $6x + 77y$ such that 
356 
$(6x + 77y) \; mod \; 6 = 5$. The solution of 
$(6x + 77y) \; mod \; 6 = 5$. The solution of 
357 
$6x + 77 = 731$ yields $x=109$. 
$6x + 77 = 731$ yields $x=109$. 
358 
\end{vworkexampleparsection} 
\end{vworkexampleparsection} 
359 
\begin{vworkexampleparsection}{Solution II (Continued Fractions)} 
\begin{vworkexampleparsection}{Solution II (Continued Fractions)} 
360 
A second (and far more efficient) way to tackle this problem 
A second (and far more efficient) way to tackle this problem 
361 
comes from the study of 
comes from the study of 
362 
continued fractions 
continued fractions 
363 
(see \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0}, 
(see \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0}, 
364 
\emph{\ccfrzeroshorttitle{}}). If the continued fraction 
\emph{\ccfrzeroshorttitle{}}). If the continued fraction 
365 
partial quotients and convergents of $a/b$ are calculated, 
partial quotients and convergents of $a/b$ are calculated, 
366 
it is guaranteed that the final convergent $p_k/q_k$ will be $a/b$ 
it is guaranteed that the final convergent $p_k/q_k$ will be $a/b$ 
367 
(because $a$ and $b$ are coprime), and the property of 
(because $a$ and $b$ are coprime), and the property of 
368 
continued fraction convergents that 
continued fraction convergents that 
369 
$q_k p_{k1}  p_k q_{k1} = (1)^k$ gives a way to choose 
$q_k p_{k1}  p_k q_{k1} = (1)^k$ gives a way to choose 
370 
$x, y$ s.t. $ax + by = 1$. With that $x,y$ known (call them 
$x, y$ s.t. $ax + by = 1$. With that $x,y$ known (call them 
371 
$x'$ and $y'$), the equation can be scaled so that 
$x'$ and $y'$), the equation can be scaled so that 
372 
choosing $x=nx'$ and $y=ny'$ will result in a solution. 
choosing $x=nx'$ and $y=ny'$ will result in a solution. 
373 
This method is not illustrated here. The important point is 
This method is not illustrated here. The important point is 
374 
that a solution can always be found. 
that a solution can always be found. 
375 
\end{vworkexampleparsection} 
\end{vworkexampleparsection} 
376 
%\vworkexamplefooter{} 
%\vworkexamplefooter{} 
377 


378 
\begin{vworktheoremstatement} 
\begin{vworktheoremstatement} 
379 
\label{thm:cpri0:ppn0:00a} 
\label{thm:cpri0:ppn0:00a} 
380 
For $a, b \in \vworkintsetpos$, the equation 
For $a, b \in \vworkintsetpos$, the equation 
381 


382 
\begin{equation} 
\begin{equation} 
383 
\label{eq:cpri0:ppn0:00a0} 
\label{eq:cpri0:ppn0:00a0} 
384 
ax + by = n 
ax + by = n 
385 
\end{equation} 
\end{equation} 
386 


387 
has integer solutions $x,y \in \vworkintset$ iff $\gcd(a,b) \vworkdivides n$. 
has integer solutions $x,y \in \vworkintset$ iff $\gcd(a,b) \vworkdivides n$. 
388 
\end{vworktheoremstatement} 
\end{vworktheoremstatement} 
389 
\begin{vworktheoremproof} 
\begin{vworktheoremproof} 
390 
First, note that choices of $x,y \in \vworkintset$ 
First, note that choices of $x,y \in \vworkintset$ 
391 
can result only in a linear combination of $a, b$ (the 
can result only in a linear combination of $a, b$ (the 
392 
lefthand side of Eq. \ref{eq:cpri0:ppn0:00a0}) which is an 
lefthand side of Eq. \ref{eq:cpri0:ppn0:00a0}) which is an 
393 
integral multiple of $\gcd(a,b)$: 
integral multiple of $\gcd(a,b)$: 
394 


395 
\begin{equation} 
\begin{equation} 
396 
\label{eq:cpri0:ppn0:00a1} 
\label{eq:cpri0:ppn0:00a1} 
397 
n = \gcd(a,b) \left( { \frac{ax}{\gcd(a,b)} + \frac{by}{\gcd(a,b)} } \right) . 
n = \gcd(a,b) \left( { \frac{ax}{\gcd(a,b)} + \frac{by}{\gcd(a,b)} } \right) . 
398 
\end{equation} 
\end{equation} 
399 


400 
Note that $a/\gcd(a,b), b/\gcd(a,b) \in \vworkintsetpos$, and note also that 
Note that $a/\gcd(a,b), b/\gcd(a,b) \in \vworkintsetpos$, and note also that 
401 
$a/\gcd(a,b)$ and $b/\gcd(a,b)$ are by definition coprime. Lemma 
$a/\gcd(a,b)$ and $b/\gcd(a,b)$ are by definition coprime. Lemma 
402 
\ref{lem:cpri0:ppn0:00a} shows that 
\ref{lem:cpri0:ppn0:00a} shows that 
403 
the linear combination of two coprime natural numbers can form 
the linear combination of two coprime natural numbers can form 
404 
any integer. Thus, through suitable choices of $x$ and $y$, any integral 
any integer. Thus, through suitable choices of $x$ and $y$, any integral 
405 
multiple of $\gcd(a,b)$ can be formed. 
multiple of $\gcd(a,b)$ can be formed. 
406 


407 
It has been shown that \emph{only} integral multiples of $\gcd(a,b)$ can 
It has been shown that \emph{only} integral multiples of $\gcd(a,b)$ can 
408 
be formed by choosing $x$ and $y$, and that 
be formed by choosing $x$ and $y$, and that 
409 
\emph{any} integral multiple of $\gcd(a,b)$ can 
\emph{any} integral multiple of $\gcd(a,b)$ can 
410 
be formed by an appropriate choice of $x$ and $y$. Thus, 
be formed by an appropriate choice of $x$ and $y$. Thus, 
411 
if $\gcd(a,b) \vworknotdivides n$, $x$ and $y$ cannot be chosen 
if $\gcd(a,b) \vworknotdivides n$, $x$ and $y$ cannot be chosen 
412 
to satisfy (\ref{eq:cpri0:ppn0:00a0}); but if 
to satisfy (\ref{eq:cpri0:ppn0:00a0}); but if 
413 
$\gcd(a,b) \vworkdivides n$, $x$ and $y$ can always be chosen 
$\gcd(a,b) \vworkdivides n$, $x$ and $y$ can always be chosen 
414 
to satisfy (\ref{eq:cpri0:ppn0:00a0}). 
to satisfy (\ref{eq:cpri0:ppn0:00a0}). 
415 
\end{vworktheoremproof} 
\end{vworktheoremproof} 
416 
\vworktheoremfooter{} 
\vworktheoremfooter{} 
417 


418 


419 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
420 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
421 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
422 
\section{The Greatest Common Divisor And Least Common Multiple} 
\section{The Greatest Common Divisor And Least Common Multiple} 
423 
%Section tag: GCD0 
%Section tag: GCD0 
424 
\label{cpri0:gcd0} 
\label{cpri0:gcd0} 
425 


426 
The \index{greatest common divisor}\index{GCD}greatest common divisor 
The \index{greatest common divisor}\index{GCD}greatest common divisor 
427 
(or GCD) and \index{least common multiple}\index{LCM}least common multiple 
(or GCD) and \index{least common multiple}\index{LCM}least common multiple 
428 
are integervalued functions of integers to which most readers 
are integervalued functions of integers to which most readers 
429 
have had exposure during elementary school. We present these functions and 
have had exposure during elementary school. We present these functions and 
430 
several of their properties both as a review and to present properties that 
several of their properties both as a review and to present properties that 
431 
are not commonly used. 
are not commonly used. 
432 


433 
\begin{vworkdefinitionstatementpar}{Greatest Common Divisor} 
\begin{vworkdefinitionstatementpar}{Greatest Common Divisor} 
434 
\label{def:cpri0:gcd0:01} 
\label{def:cpri0:gcd0:01} 
435 
The \emph{greatest common divisor} of two positive integers 
The \emph{greatest common divisor} of two positive integers 
436 
$a$ and $b$, denoted $\gcd(a,b)$, is the largest integer 
$a$ and $b$, denoted $\gcd(a,b)$, is the largest integer 
437 
that divides both $a$ and $b$. 
that divides both $a$ and $b$. 
438 
\end{vworkdefinitionstatementpar} 
\end{vworkdefinitionstatementpar} 
439 


440 
\begin{vworklemmastatement} 
\begin{vworklemmastatement} 
441 
\label{lem:cpri0:gcd0:01} 
\label{lem:cpri0:gcd0:01} 
442 
For $a,b \in \vworkintsetpos$, 
For $a,b \in \vworkintsetpos$, 
443 


444 
\begin{equation} 
\begin{equation} 
445 
\label{eq:lem:cpri0:gcd0:01:01} 
\label{eq:lem:cpri0:gcd0:01:01} 
446 
\gcd(a,b) = \gcd(a, b + a). 
\gcd(a,b) = \gcd(a, b + a). 
447 
\end{equation} 
\end{equation} 
448 
\end{vworklemmastatement} 
\end{vworklemmastatement} 
449 
\begin{vworklemmaproof} 
\begin{vworklemmaproof} 
450 
For an integer $g \in \vworkintsetpos$, if 
For an integer $g \in \vworkintsetpos$, if 
451 
$g \vworkdivides a$ and $g \vworkdivides b$, then 
$g \vworkdivides a$ and $g \vworkdivides b$, then 
452 
$g \vworkdivides (b+a)$. If $g \vworknotdivides b$ 
$g \vworkdivides (b+a)$. If $g \vworknotdivides b$ 
453 
and $g \vworkdivides a$, then $g \vworknotdivides (b+a)$. 
and $g \vworkdivides a$, then $g \vworknotdivides (b+a)$. 
454 
Thus any integer 
Thus any integer 
455 
$g$ which divides both $a$ and $b$ also divides both 
$g$ which divides both $a$ and $b$ also divides both 
456 
$a$ and $b+a$, and any integer which either does not 
$a$ and $b+a$, and any integer which either does not 
457 
divide $a$ or does not divide $b$ cannot divide 
divide $a$ or does not divide $b$ cannot divide 
458 
both $a$ and $b+a$. 
both $a$ and $b+a$. 
459 


460 
The greatest common divisor of $a$ and $b$ is defined as the 
The greatest common divisor of $a$ and $b$ is defined as the 
461 
largest integer which divides both $a$ and $b$. Because of 
largest integer which divides both $a$ and $b$. Because of 
462 
the relationship described above, the largest integer which 
the relationship described above, the largest integer which 
463 
divides both $a$ and $b$ is also the largest integer which 
divides both $a$ and $b$ is also the largest integer which 
464 
divides both $a$ and $b+a$, proving 
divides both $a$ and $b+a$, proving 
465 
(\ref{eq:lem:cpri0:gcd0:01:01}) and the lemma. 
(\ref{eq:lem:cpri0:gcd0:01:01}) and the lemma. 
466 
\end{vworklemmaproof} 
\end{vworklemmaproof} 
467 
\vworklemmafooter{} 
\vworklemmafooter{} 
468 


469 


470 


471 


472 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
473 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
474 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
475 
\section{Acknowledgements} 
\section{Acknowledgements} 
476 
%Section tag: ACK0 
%Section tag: ACK0 
477 


478 
We would like to gratefully acknowledge the assistance of 
We would like to gratefully acknowledge the assistance of 
479 
Iain Davidson\index{Davidson, Iain} \cite{bibref:i:iaindavidson}, 
Iain Davidson\index{Davidson, Iain} \cite{bibref:i:iaindavidson}, 
480 
G\'erard Nin\index{Nin, Gerard@Nin, G\'erard} \cite{bibref:i:gerardnin}, 
G\'erard Nin\index{Nin, Gerard@Nin, G\'erard} \cite{bibref:i:gerardnin}, 
481 
and Tim Robinson\index{Robinson, Tim} \cite{bibref:i:timrobinson} 
and Tim Robinson\index{Robinson, Tim} \cite{bibref:i:timrobinson} 
482 
with Lemmas \ref{lem:cpri0:ppn0:000p} and \ref{lem:cpri0:ppn0:00a} 
with Lemmas \ref{lem:cpri0:ppn0:000p} and \ref{lem:cpri0:ppn0:00a} 
483 
and Example \ref{ex:cpri0:ppn0:01}. 
and Example \ref{ex:cpri0:ppn0:01}. 
484 


485 


486 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
487 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
488 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
489 
\section{Exercises} 
\section{Exercises} 
490 
%Section tag: EXE0 
%Section tag: EXE0 
491 


492 


493 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
494 


495 
\noindent\begin{figure}[!b] 
\noindent\begin{figure}[!b] 
496 
\noindent\rule[0.25in]{\textwidth}{1pt} 
\noindent\rule[0.25in]{\textwidth}{1pt} 
497 
\begin{tiny} 
\begin{tiny} 
498 
\begin{verbatim} 
\begin{verbatim} 
499 
$RCSfile: c_pri0.tex,v $ 
$RCSfile: c_pri0.tex,v $ 
500 
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_pri0/c_pri0.tex,v $ 
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_pri0/c_pri0.tex,v $ 
501 
$Revision: 1.6 $ 
$Revision: 1.6 $ 
502 
$Author: dtashley $ 
$Author: dtashley $ 
503 
$Date: 2003/11/30 01:18:17 $ 
$Date: 2003/11/30 01:18:17 $ 
504 
\end{verbatim} 
\end{verbatim} 
505 
\end{tiny} 
\end{tiny} 
506 
\noindent\rule[0.25in]{\textwidth}{1pt} 
\noindent\rule[0.25in]{\textwidth}{1pt} 
507 
\end{figure} 
\end{figure} 
508 


509 


510 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
511 
% $Log: c_pri0.tex,v $ 
% $Log: c_pri0.tex,v $ 
512 
% Revision 1.6 2003/11/30 01:18:17 dtashley 
% Revision 1.6 2003/11/30 01:18:17 dtashley 
513 
% Chapter modified to eliminate double horizontal lines. 
% Chapter modified to eliminate double horizontal lines. 
514 
% 
% 
515 
% Revision 1.5 2003/04/03 19:49:36 dtashley 
% Revision 1.5 2003/04/03 19:49:36 dtashley 
516 
% Global corrections to typeface of "gcd" made as per JanHinnerk Reichert's 
% Global corrections to typeface of "gcd" made as per JanHinnerk Reichert's 
517 
% recommendation. 
% recommendation. 
518 
% 
% 
519 
% Revision 1.4 2003/03/25 05:31:22 dtashley 
% Revision 1.4 2003/03/25 05:31:22 dtashley 
520 
% Lemma about gcd()'s added, specifically that gcd(a,b)=gcd(a,b+a). 
% Lemma about gcd()'s added, specifically that gcd(a,b)=gcd(a,b+a). 
521 
% 
% 
522 
% Revision 1.3 2002/07/29 16:30:09 dtashley 
% Revision 1.3 2002/07/29 16:30:09 dtashley 
523 
% Safety checkin before moving work back to WSU server Kalman. 
% Safety checkin before moving work back to WSU server Kalman. 
524 
% 
% 
525 
% Revision 1.2 2001/07/01 19:32:06 dtashley 
% Revision 1.2 2001/07/01 19:32:06 dtashley 
526 
% Move out of binary mode for use with CVS. 
% Move out of binary mode for use with CVS. 
527 
% 
% 
528 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
529 
% $History: c_pri0.tex $ 
% $History: c_pri0.tex $ 
530 
% 
% 
531 
% ***************** Version 10 ***************** 
% ***************** Version 10 ***************** 
532 
% User: Dashley1 Date: 3/07/01 Time: 12:17a 
% User: Dashley1 Date: 3/07/01 Time: 12:17a 
533 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
534 
% Edits. 
% Edits. 
535 
% 
% 
536 
% ***************** Version 9 ***************** 
% ***************** Version 9 ***************** 
537 
% User: Dashley1 Date: 2/10/01 Time: 2:03a 
% User: Dashley1 Date: 2/10/01 Time: 2:03a 
538 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
539 
% Completion of Farey series chapter. 
% Completion of Farey series chapter. 
540 
% 
% 
541 
% ***************** Version 8 ***************** 
% ***************** Version 8 ***************** 
542 
% User: Dashley1 Date: 1/31/01 Time: 4:20p 
% User: Dashley1 Date: 1/31/01 Time: 4:20p 
543 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
544 
% Edits. 
% Edits. 
545 
% 
% 
546 
% ***************** Version 7 ***************** 
% ***************** Version 7 ***************** 
547 
% User: Dashley1 Date: 12/22/00 Time: 12:56a 
% User: Dashley1 Date: 12/22/00 Time: 12:56a 
548 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
549 
% Tcl automated method of build refined. 
% Tcl automated method of build refined. 
550 
% 
% 
551 
% ***************** Version 6 ***************** 
% ***************** Version 6 ***************** 
552 
% User: David T. Ashley Date: 8/12/00 Time: 9:48p 
% User: David T. Ashley Date: 8/12/00 Time: 9:48p 
553 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
554 
% Edits. 
% Edits. 
555 
% 
% 
556 
% ***************** Version 5 ***************** 
% ***************** Version 5 ***************** 
557 
% User: David T. Ashley Date: 8/06/00 Time: 8:50a 
% User: David T. Ashley Date: 8/06/00 Time: 8:50a 
558 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
559 
% Work on Prime Number and Farey Series chapters. 
% Work on Prime Number and Farey Series chapters. 
560 
% 
% 
561 
% ***************** Version 4 ***************** 
% ***************** Version 4 ***************** 
562 
% User: David T. Ashley Date: 7/30/00 Time: 8:22p 
% User: David T. Ashley Date: 7/30/00 Time: 8:22p 
563 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
564 
% Edits. 
% Edits. 
565 
% 
% 
566 
% ***************** Version 3 ***************** 
% ***************** Version 3 ***************** 
567 
% User: David T. Ashley Date: 7/29/00 Time: 11:50p 
% User: David T. Ashley Date: 7/29/00 Time: 11:50p 
568 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
569 
% Edits, addition of solutions manual volume. 
% Edits, addition of solutions manual volume. 
570 
% 
% 
571 
% ***************** Version 2 ***************** 
% ***************** Version 2 ***************** 
572 
% User: David T. Ashley Date: 7/09/00 Time: 11:23p 
% User: David T. Ashley Date: 7/09/00 Time: 11:23p 
573 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
% Updated in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
574 
% Addition of new chapters, enhancements to preface. 
% Addition of new chapters, enhancements to preface. 
575 
% 
% 
576 
% ***************** Version 1 ***************** 
% ***************** Version 1 ***************** 
577 
% User: David T. Ashley Date: 7/09/00 Time: 9:24p 
% User: David T. Ashley Date: 7/09/00 Time: 9:24p 
578 
% Created in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
% Created in $/uC Software MultiVolume Book (A)/Chapter, PRI0, Prime Numbers 
579 
% Initial checkin. 
% Initial checkin. 
580 
%End of file C_PRI0.TEX 
%End of file C_PRI0.TEX 