/[dtapublic]/pubs/books/ucbka/trunk/c_pri0/c_pri0.tex
ViewVC logotype

Diff of /pubs/books/ucbka/trunk/c_pri0/c_pri0.tex

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 6 by dashley, Fri Oct 7 01:36:46 2016 UTC revision 140 by dashley, Mon Jul 3 01:59:16 2017 UTC
# Line 1  Line 1 
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{non-negative integer}\index{non-negative integer}\index{integer!non-negative}  A \emph{non-negative integer}\index{non-negative integer}\index{integer!non-negative}
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 non-negative  such as 0, 1, 2, 3, \ldots{}.  In this work, the set of non-negative
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 natural-number factors only 1 and itself.  which has as its natural-number 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 readers---presumably being in predominantly technical vocations---are  of our readers---presumably being in predominantly technical vocations---are
153  probably familiar with most of these properties.  probably familiar with most of these properties.
154    
155  Prime numbers are the fundamental currency of arithmetic---the fundamental  Prime numbers are the fundamental currency of arithmetic---the 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 result---that such a factorization  Arithmetic), establishes a stronger result---that 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  ax-by =  ax-by =
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{} , (a-2)b \; mod \; a, (a-1)b \; mod \; a \} .  \ldots{} , (a-2)b \; mod \; a, (a-1)b \; mod \; a \} .
292  \end{equation}  \end{equation}
293    
294  Note in this set that each integer $\{0, \ldots, a-1 \}$  Note in this set that each integer $\{0, \ldots, a-1 \}$
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, a-1 \}$ is present exactly once, note that  $\{0, \ldots, a-1 \}$ 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, a-1 \}$.  In order for each  element is $\in \{0, \ldots, a-1 \}$.  In order for each
300  integer $\{0, \ldots, a-1 \}$ \emph{not} to be present  integer $\{0, \ldots, a-1 \}$ \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 a-1$.  In that case,  with $p \neq q$ and $0 \leq p,q \leq a-1$.  In that case,
305  we would have $(q-p) b = ka$.  Because $a$ and $b$ are  we would have $(q-p) b = ka$.  Because $a$ and $b$ are
306  coprime (share no prime factors), this would require $(q-p)$  coprime (share no prime factors), this would require $(q-p)$
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  $(q-p) \geq a$, a contradiction.  Thus, there are no  $(q-p) \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, a-1 \}$ is present.  every integer $\{0, \ldots, a-1 \}$ 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} apply---only  and Equation \ref{eq:cpri0:ppn0:00a1} apply---only
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_{k-1} - p_k q_{k-1} = (-1)^k$ gives a way to choose  $q_k p_{k-1} - p_k q_{k-1} = (-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  left-hand side of Eq. \ref{eq:cpri0:ppn0:00a0}) which is an  left-hand 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 integer-valued functions of integers to which most readers  are integer-valued 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 Jan-Hinnerk Reichert's  % Global corrections to typeface of "gcd" made as per Jan-Hinnerk 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 Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers  % Updated in $/uC Software Multi-Volume 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 Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers  % Updated in $/uC Software Multi-Volume 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 Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers  % Updated in $/uC Software Multi-Volume 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 Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers  % Updated in $/uC Software Multi-Volume 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 Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers  % Updated in $/uC Software Multi-Volume 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 Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers  % Updated in $/uC Software Multi-Volume 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 Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers  % Updated in $/uC Software Multi-Volume 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 Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers  % Updated in $/uC Software Multi-Volume 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 Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers  % Updated in $/uC Software Multi-Volume 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 Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers  % Created in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers
579  % Initial check-in.  % Initial check-in.
580  %End of file C_PRI0.TEX  %End of file C_PRI0.TEX

Legend:
Removed from v.6  
changed lines
  Added in v.140

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25