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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 6 - (hide annotations) (download) (as text)
Fri Oct 7 01:36:46 2016 UTC (7 years, 1 month ago) by dashley
File MIME type: application/x-tex
File size: 23315 byte(s)
Initial commit after migrating from CVS.
1 dashley 6 %$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 $
2    
3     \chapter[\cprizeroshorttitle{}]{\cprizerolongtitle{}}
4    
5     \label{cpri0}
6    
7     \beginchapterquote{``The number of primes less than 1,000,000,000 is
8     50,847,478: this is enough for an engineer, and he
9     can be perfectly happy without the rest.''}
10     {G.H. Hardy \cite{bibref:b:mathematiciansapology:1940}, p. 102}
11    
12     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
13     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
14     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
15     \section{Introduction}
16     %Section Tag INT0
17     \label{cpri0:int0}
18    
19     This chapter presents important properties of integers and prime numbers; and
20     related topics and concepts. Nearly all of the ideas presented come from
21     number theory (a branch of mathematics).
22    
23     Our aim in this chapter is to provide the reader
24     with the background necessary to understand other
25     topics in the work (Farey series,
26     continued fractions, and rational approximation).
27     Because this work is concerned with microcontroller
28     software development (rather than mathematics),
29     the treatment is regrettably minimal.
30    
31    
32     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
33     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
34     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
35     \section{Sets Of Integers}
36     %Section tag: SOI0
37     \label{cpri0:soi0}
38    
39     An\index{integer}\index{sets of integers}\index{integer!sets of}
40     \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}).
42     The set of integers is denoted $\vworkintset$:\index{Z@$\vworkintset$}%
43     \index{integer!Z@$\vworkintset$}
44    
45     \begin{equation}
46     \vworkintset = \{ \ldots{} , -3, -2, -1, 0, 1, 2, 3, \ldots{} \}.
47     \end{equation}
48    
49     A \emph{natural number}\index{natural number}\index{counting number}
50     \index{integer!natural number}\index{integer!counting number} (or \emph{counting number})
51     is a positive integer,
52     such as 1, 2, 3, \ldots{} (\cite{bibref:b:penguindictionaryofmathematics:2ded}).
53     In this work, the set of natural numbers is denoted
54     $\vworkintsetpos$:\index{N@$\vworkintsetpos$}\index{integer!N@$\vworkintsetpos$}
55    
56     \begin{equation}
57     \vworkintsetpos = \{ 1, 2, 3, 4, 5, \ldots{} \}.
58     \end{equation}
59    
60     A \emph{non-negative integer}\index{non-negative integer}\index{integer!non-negative}
61     is an integer which is not negative,
62     such as 0, 1, 2, 3, \ldots{}. In this work, the set of non-negative
63     integers is denoted $\vworkintsetnonneg$:\footnote{This notation is
64     somewhat unconventional, as in most works $\vworkintsetnonneg$ denotes
65     the set of natural numbers; see \cite{bibref:b:penguindictionaryofmathematics:2ded},
66     p. 223.}\index{Z+@$\vworkintsetnonneg$}\index{integer!Z+@$\vworkintsetnonneg$}
67    
68     \begin{equation}
69     \vworkintsetnonneg = \{ 0, 1, 2, 3, 4, \ldots{} \}.
70     \end{equation}
71    
72     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
73     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
74     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
75     \section{Divisibility Of Integers With No Remainder}
76     \label{cpri0:doi0}
77    
78     We follow the convention of \cite{bibref:b:HardyAndWrightClassic}
79     and use `$\vworkdivides$'
80     \index{divides@divides ($\vworkdivides$)}
81     \index{--@$\vworkdivides$ (divides)}
82     to denote that one integer can divide
83     another with no remainder, and use `$\vworknotdivides$'
84     \index{divides@divides ($\vworkdivides$)}
85     \index{--@$\vworknotdivides$ (doesn't divide)}
86     to denote
87     that one integer cannot divide another without a
88     remainder. $a \vworkdivides b$, read ``$a$
89     divides $b$'', denotes that $b/a$ has no remainder; and
90     $a \vworknotdivides b$, read ``$a$ does not divide $b$'', denotes
91     that $b/a$ has a remainder.
92    
93     The following implications (\cite{bibref:b:HardyAndWrightClassic}, p. 1)
94     are intuitively plain, and we accept them without proof.
95    
96     \begin{equation}
97     b \vworkdivides a \wedge c \vworkdivides b \vworkhimp c \vworkdivides a
98     \end{equation}
99    
100     \begin{equation}
101     b \vworkdivides a \vworkhimp b c \vworkdivides a c
102     \end{equation}
103    
104     \begin{equation}
105     c \vworkdivides a \wedge c \vworkdivides b \vworkhimp c \vworkdivides (m a + n b)
106     \end{equation}
107    
108    
109     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
110     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
111     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
112     \section{Prime Numbers And Composite Numbers}
113     %Section tag: PNC0
114     \label{cpri0:pnc0}
115    
116     A \emph{prime number}\index{prime number} (or, more tersely, a \emph{prime})
117     is a natural number
118     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
120     a \emph{composite number}\index{composite number} (or just a \emph{composite}).
121     The number `1' is considered neither prime nor composite.
122    
123     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
125     $4 = 2 \times 2$,
126     $6 = 2 \times 3$,
127     $8 = 2 \times 2 \times 2$,
128     $9 = 3 \times 3$,
129     $10 = 2 \times 5$,
130     $12 = 2 \times 2 \times 3$,
131     $14 = 2 \times 7$,
132     $15 = 3 \times 5$,
133     $16 = 2 \times 2 \times 2 \times 2$,
134     and $18 = 2 \times 3 \times 3$.
135    
136     Many properties of prime numbers were understood even prior
137     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
139     were discovered relatively recently (1600 A.D. and later). In recent history,
140     the difficulty of factoring large composite numbers into their [large] prime
141     components has become a linchpin of cryptography.
142    
143    
144     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
145     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
146     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
147     \section{Properties Of Prime Numbers}
148     %Subsection Tag: PPN0
149     \label{cpri0:ppn0}
150    
151     This section presents several important properties of prime numbers. Most
152     of our readers---presumably being in predominantly technical vocations---are
153     probably familiar with most of these properties.
154    
155     Prime numbers are the fundamental currency of arithmetic---the fundamental
156     atomic ``stuff'' from which all integers are constructed. The first properties
157     presented involve this aspect of primes. The presentation and the
158     presentation order in
159     \cite{bibref:b:HardyAndWrightClassic} is perfect, so we don't deviate.
160    
161     \begin{vworktheoremstatement}
162     \label{thm:cpri0:ppn0:00}
163     Every positive integer, except 1, is a product of primes.
164     \end{vworktheoremstatement}
165     \begin{vworktheoremproof}
166     See \cite{bibref:b:HardyAndWrightClassic}, p. 2.
167     \end{vworktheoremproof}
168     \vworktheoremfooter{}
169    
170     When a number is factored into its prime components, we
171     follow \cite{bibref:b:HardyAndWrightClassic}, p. 2 in defining
172     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
175     into prime components. Theorem \ref{thm:cpri0:ppn0:01} (The Fundamental Theorem Of
176     Arithmetic), establishes a stronger result---that such a factorization
177     is unique.
178    
179     \begin{equation}
180     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)
182     \end{equation}
183    
184     \begin{vworktheoremstatementpar}{The Fundamental Theorem Of Arithmetic}
185     \label{thm:cpri0:ppn0:01}
186     (\cite{bibref:b:HardyAndWrightClassic}, p. 3) The standard form of
187     $n$ is unique; apart from the rearrangement of factors, $n$ can be
188     expressed as a product of primes in one way only.
189     \end{vworktheoremstatementpar}
190     \begin{vworktheoremproof}
191     See \cite{bibref:b:HardyAndWrightClassic}, p. 21.
192     \end{vworktheoremproof}
193     \vworktheoremfooter{}
194    
195     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
197     that there is no largest prime number and that there is an infinite number
198     of prime numbers.
199     Euclid's famous proof that there is no largest prime number is reproduced below.
200    
201     \begin{vworktheoremstatementpar}{Euclid's Second Theorem}
202     The number of primes is infinite.\index{Euclid}\index{Euclid!Second Theorem}%
203     \index{prime number!no largest prime number}
204     \end{vworktheoremstatementpar}
205     \begin{vworktheoremproof}
206     (\cite{bibref:b:HardyAndWrightClassic}, p.12) Assume there is a largest
207     prime number, denoted $p$. Let
208     $2 \times 3 \times 5 \times \ldots \times p$ be the aggregate (i.e. product)
209     of primes up to $p$, and let
210    
211     \begin{equation}
212     q = (2 \times 3 \times 5 \times \ldots{} \times p) + 1.
213     \end{equation}
214    
215     $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
217     either case there is a prime greater than $p$, which is a contradiction, and
218     proves the theorem.
219     \end{vworktheoremproof}
220     %\vworktheoremfooter{}
221    
222     \begin{vworktheoremstatementpar}{Euclid's First Theorem}
223     \index{Euclid}\index{Euclid!First Theorem}%
224     If $p$ is prime and $p \vworkdivides{} a b$, then $p \vworkdivides{} a$
225     or $p \vworkdivides{} b$.
226     \end{vworktheoremstatementpar}
227     \begin{vworktheoremproof}
228     Waiting on information for the proof.
229     \end{vworktheoremproof}
230     \begin{vworktheoremparsection}{Remarks}
231     \begin{itemize}
232     \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
234     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.
236     \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$,
238     but $6 \vworknotdivides{} 10$ and $6 \vworknotdivides{} 21$.
239    
240     \end{itemize}
241     \end{vworktheoremparsection}
242     %\vworktheoremfooter{}
243    
244     \begin{vworklemmastatement}
245     \label{lem:cpri0:ppn0:000p}
246     For $a, b, x, y \in \vworkintsetpos$, if
247    
248     \begin{equation}
249     ax - by = 1 ,
250     \end{equation}
251    
252     then $a$ and $b$ are coprime.
253     \end{vworklemmastatement}
254     \begin{vworklemmaproof}
255     Assume that $a$ and $b$ are \emph{not} coprime,
256     i.e. that $\gcd(a,b) > 1$. Then
257    
258     \begin{equation}
259     ax-by =
260     \gcd(a,b) \left( { \frac{ax}{\gcd(a,b)}-\frac{by}{\gcd(a,b)}} \right)
261     \neq 1 ,
262     \end{equation}
263    
264     since $\gcd(a,b) > 1$.
265     \end{vworklemmaproof}
266     %\vworklemmafooter{}
267    
268     \begin{vworklemmastatement}
269     \label{lem:cpri0:ppn0:00a}
270     The equation
271    
272     \begin{equation}
273     ax + by = n
274     \end{equation}
275    
276     (with $a,b \in \vworkintsetpos$) is soluble in integers
277     $x,y \in \vworkintset$ for any $n \in \vworkintset$ iff
278     $a$ and $b$ are coprime.
279     \end{vworklemmastatement}
280     \begin{vworklemmaproof}
281     First, it will be shown that if $a$ and $b$ are coprime,
282     any $n$ can be reached through some choice of
283     $x,y \in \vworkintset$. (In fact, we give a
284     procedure for choosing $x$ and $y$.)
285    
286     Form the set
287    
288     \begin{equation}
289     \label{eq:cpri0:ppn0:00a00}
290     \{ 0b \; mod \; a, 1b \; mod \; a, 2b \; mod \; a,
291     \ldots{} , (a-2)b \; mod \; a, (a-1)b \; mod \; a \} .
292     \end{equation}
293    
294     Note in this set that each integer $\{0, \ldots, a-1 \}$
295     is present exactly once, but not necessarily in order.
296     To show that each integer
297     $\{0, \ldots, a-1 \}$ is present exactly once, note that
298     the set contains exactly $a$ elements, and note that each
299     element is $\in \{0, \ldots, a-1 \}$. In order for each
300     integer $\{0, \ldots, a-1 \}$ \emph{not} to be present
301     exactly once, the set must contain at least one duplication
302     of an element. Assume that a duplication exists, namely
303     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,
305     we would have $(q-p) b = ka$. Because $a$ and $b$ are
306     coprime (share no prime factors), this would require $(q-p)$
307     to have at least every prime factor in $a$ with at least the
308     same multiplicity as $a$, which would imply that
309     $(q-p) \geq a$, a contradiction. Thus, there are no
310     duplicates in the set (\ref{eq:cpri0:ppn0:00a00}), and
311     every integer $\{0, \ldots, a-1 \}$ is present.
312    
313     It is clear then that $x$ and $y$ can always be chosen by
314     ``modulo shopping''. We could, for example,
315     calculate $n \; mod \; a$, and find some $y$
316     s.t. $yb \; mod \; a = n \; mod \; a$, then choose $x$.\footnote{It
317     is guaranteed
318     that we \emph{can} find such an $x$ because
319     the choice of $x$ moves $n$ in steps
320     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
322     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}.
324    
325     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
327     in Theorem \ref{thm:cpri0:ppn0:00a}
328     and Equation \ref{eq:cpri0:ppn0:00a1} apply---only
329     $n$ which are multiples of $\gcd(a,b)$ can be
330     ``reached'', no matter what $x$ and $y$ are chosen.
331     \end{vworklemmaproof}
332     %\vworklemmafooter{}
333    
334     \begin{vworkexamplestatement}
335     \label{ex:cpri0:ppn0:01}
336     Find integers $x$ and $y$ such that
337    
338     \begin{equation}
339     6 x + 77 y = 731
340     \end{equation}
341     \end{vworkexamplestatement}
342     \begin{vworkexampleparsection}{Solution I (``Modulo Shopping'')}
343     First, fix $y$ using the ``modulo shopping'' method
344     suggested by Lemma \ref{lem:cpri0:ppn0:00a}. Building
345     the set
346    
347     \begin{equation}
348     \{ 0 \; mod \; 6, 77 \; mod \; 6, 154 \; mod \; 6,
349     231 \; mod \; 6, 308 \; mod \; 6, 385 \; mod \; 6 \}
350     \end{equation}
351    
352     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
354     element in the sets above). With $y$ fixed at 1, any choice
355     of $x$ will yield a result $6x + 77y$ such that
356     $(6x + 77y) \; mod \; 6 = 5$. The solution of
357     $6x + 77 = 731$ yields $x=109$.
358     \end{vworkexampleparsection}
359     \begin{vworkexampleparsection}{Solution II (Continued Fractions)}
360     A second (and far more efficient) way to tackle this problem
361     comes from the study of
362     continued fractions
363     (see \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0},
364     \emph{\ccfrzeroshorttitle{}}). If the continued fraction
365     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$
367     (because $a$ and $b$ are coprime), and the property of
368     continued fraction convergents that
369     $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
371     $x'$ and $y'$), the equation can be scaled so that
372     choosing $x=nx'$ and $y=ny'$ will result in a solution.
373     This method is not illustrated here. The important point is
374     that a solution can always be found.
375     \end{vworkexampleparsection}
376     %\vworkexamplefooter{}
377    
378     \begin{vworktheoremstatement}
379     \label{thm:cpri0:ppn0:00a}
380     For $a, b \in \vworkintsetpos$, the equation
381    
382     \begin{equation}
383     \label{eq:cpri0:ppn0:00a0}
384     ax + by = n
385     \end{equation}
386    
387     has integer solutions $x,y \in \vworkintset$ iff $\gcd(a,b) \vworkdivides n$.
388     \end{vworktheoremstatement}
389     \begin{vworktheoremproof}
390     First, note that choices of $x,y \in \vworkintset$
391     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
393     integral multiple of $\gcd(a,b)$:
394    
395     \begin{equation}
396     \label{eq:cpri0:ppn0:00a1}
397     n = \gcd(a,b) \left( { \frac{ax}{\gcd(a,b)} + \frac{by}{\gcd(a,b)} } \right) .
398     \end{equation}
399    
400     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
402     \ref{lem:cpri0:ppn0:00a} shows that
403     the linear combination of two coprime natural numbers can form
404     any integer. Thus, through suitable choices of $x$ and $y$, any integral
405     multiple of $\gcd(a,b)$ can be formed.
406    
407     It has been shown that \emph{only} integral multiples of $\gcd(a,b)$ can
408     be formed by choosing $x$ and $y$, and that
409     \emph{any} integral multiple of $\gcd(a,b)$ can
410     be formed by an appropriate choice of $x$ and $y$. Thus,
411     if $\gcd(a,b) \vworknotdivides n$, $x$ and $y$ cannot be chosen
412     to satisfy (\ref{eq:cpri0:ppn0:00a0}); but if
413     $\gcd(a,b) \vworkdivides n$, $x$ and $y$ can always be chosen
414     to satisfy (\ref{eq:cpri0:ppn0:00a0}).
415     \end{vworktheoremproof}
416     \vworktheoremfooter{}
417    
418    
419     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
420     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
421     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
422     \section{The Greatest Common Divisor And Least Common Multiple}
423     %Section tag: GCD0
424     \label{cpri0:gcd0}
425    
426     The \index{greatest common divisor}\index{GCD}greatest common divisor
427     (or GCD) and \index{least common multiple}\index{LCM}least common multiple
428     are integer-valued functions of integers to which most readers
429     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
431     are not commonly used.
432    
433     \begin{vworkdefinitionstatementpar}{Greatest Common Divisor}
434     \label{def:cpri0:gcd0:01}
435     The \emph{greatest common divisor} of two positive integers
436     $a$ and $b$, denoted $\gcd(a,b)$, is the largest integer
437     that divides both $a$ and $b$.
438     \end{vworkdefinitionstatementpar}
439    
440     \begin{vworklemmastatement}
441     \label{lem:cpri0:gcd0:01}
442     For $a,b \in \vworkintsetpos$,
443    
444     \begin{equation}
445     \label{eq:lem:cpri0:gcd0:01:01}
446     \gcd(a,b) = \gcd(a, b + a).
447     \end{equation}
448     \end{vworklemmastatement}
449     \begin{vworklemmaproof}
450     For an integer $g \in \vworkintsetpos$, if
451     $g \vworkdivides a$ and $g \vworkdivides b$, then
452     $g \vworkdivides (b+a)$. If $g \vworknotdivides b$
453     and $g \vworkdivides a$, then $g \vworknotdivides (b+a)$.
454     Thus any integer
455     $g$ which divides both $a$ and $b$ also divides both
456     $a$ and $b+a$, and any integer which either does not
457     divide $a$ or does not divide $b$ cannot divide
458     both $a$ and $b+a$.
459    
460     The greatest common divisor of $a$ and $b$ is defined as the
461     largest integer which divides both $a$ and $b$. Because of
462     the relationship described above, the largest integer which
463     divides both $a$ and $b$ is also the largest integer which
464     divides both $a$ and $b+a$, proving
465     (\ref{eq:lem:cpri0:gcd0:01:01}) and the lemma.
466     \end{vworklemmaproof}
467     \vworklemmafooter{}
468    
469    
470    
471    
472     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
473     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
474     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
475     \section{Acknowledgements}
476     %Section tag: ACK0
477    
478     We would like to gratefully acknowledge the assistance of
479     Iain Davidson\index{Davidson, Iain} \cite{bibref:i:iaindavidson},
480     G\'erard Nin\index{Nin, Gerard@Nin, G\'erard} \cite{bibref:i:gerardnin},
481     and Tim Robinson\index{Robinson, Tim} \cite{bibref:i:timrobinson}
482     with Lemmas \ref{lem:cpri0:ppn0:000p} and \ref{lem:cpri0:ppn0:00a}
483     and Example \ref{ex:cpri0:ppn0:01}.
484    
485    
486     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
487     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
488     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
489     \section{Exercises}
490     %Section tag: EXE0
491    
492    
493     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
494    
495     \noindent\begin{figure}[!b]
496     \noindent\rule[-0.25in]{\textwidth}{1pt}
497     \begin{tiny}
498     \begin{verbatim}
499     $RCSfile: c_pri0.tex,v $
500     $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_pri0/c_pri0.tex,v $
501     $Revision: 1.6 $
502     $Author: dtashley $
503     $Date: 2003/11/30 01:18:17 $
504     \end{verbatim}
505     \end{tiny}
506     \noindent\rule[0.25in]{\textwidth}{1pt}
507     \end{figure}
508    
509    
510     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
511     % $Log: c_pri0.tex,v $
512     % Revision 1.6 2003/11/30 01:18:17 dtashley
513     % Chapter modified to eliminate double horizontal lines.
514     %
515     % Revision 1.5 2003/04/03 19:49:36 dtashley
516     % Global corrections to typeface of "gcd" made as per Jan-Hinnerk Reichert's
517     % recommendation.
518     %
519     % 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).
521     %
522     % Revision 1.3 2002/07/29 16:30:09 dtashley
523     % Safety checkin before moving work back to WSU server Kalman.
524     %
525     % Revision 1.2 2001/07/01 19:32:06 dtashley
526     % Move out of binary mode for use with CVS.
527     %
528     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
529     % $History: c_pri0.tex $
530     %
531     % ***************** Version 10 *****************
532     % User: Dashley1 Date: 3/07/01 Time: 12:17a
533     % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers
534     % Edits.
535     %
536     % ***************** Version 9 *****************
537     % User: Dashley1 Date: 2/10/01 Time: 2:03a
538     % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers
539     % Completion of Farey series chapter.
540     %
541     % ***************** Version 8 *****************
542     % User: Dashley1 Date: 1/31/01 Time: 4:20p
543     % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers
544     % Edits.
545     %
546     % ***************** Version 7 *****************
547     % User: Dashley1 Date: 12/22/00 Time: 12:56a
548     % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers
549     % Tcl automated method of build refined.
550     %
551     % ***************** Version 6 *****************
552     % User: David T. Ashley Date: 8/12/00 Time: 9:48p
553     % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers
554     % Edits.
555     %
556     % ***************** Version 5 *****************
557     % User: David T. Ashley Date: 8/06/00 Time: 8:50a
558     % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers
559     % Work on Prime Number and Farey Series chapters.
560     %
561     % ***************** Version 4 *****************
562     % User: David T. Ashley Date: 7/30/00 Time: 8:22p
563     % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers
564     % Edits.
565     %
566     % ***************** Version 3 *****************
567     % User: David T. Ashley Date: 7/29/00 Time: 11:50p
568     % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers
569     % Edits, addition of solutions manual volume.
570     %
571     % ***************** Version 2 *****************
572     % User: David T. Ashley Date: 7/09/00 Time: 11:23p
573     % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers
574     % Addition of new chapters, enhancements to preface.
575     %
576     % ***************** Version 1 *****************
577     % User: David T. Ashley Date: 7/09/00 Time: 9:24p
578     % Created in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers
579     % Initial check-in.
580     %End of file C_PRI0.TEX

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25