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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 6 - (show annotations) (download) (as text)
Fri Oct 7 01:36:46 2016 UTC (8 years, 1 month ago) by dashley
File MIME type: application/x-tex
File size: 23315 byte(s)
Initial commit after migrating from CVS.
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 $
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