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

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 46 \vworkintset = \{ \ldots{} , -3, -2, -1, 0, 1, 2, 3, \ldots{} \}. 47 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 57 \vworkintsetpos = \{ 1, 2, 3, 4, 5, \ldots{} \}. 58 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 69 \vworkintsetnonneg = \{ 0, 1, 2, 3, 4, \ldots{} \}. 70 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 97 b \vworkdivides a \wedge c \vworkdivides b \vworkhimp c \vworkdivides a 98 99 100 101 b \vworkdivides a \vworkhimp b c \vworkdivides a c 102 103 104 105 c \vworkdivides a \wedge c \vworkdivides b \vworkhimp c \vworkdivides (m a + n b) 106 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 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 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 212 q = (2 \times 3 \times 5 \times \ldots{} \times p) + 1. 213 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 249 ax - by = 1 , 250 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 259 ax-by = 260 \gcd(a,b) \left( { \frac{ax}{\gcd(a,b)}-\frac{by}{\gcd(a,b)}} \right) 261 \neq 1 , 262 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 273 ax + by = n 274 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 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 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 339 6 x + 77 y = 731 340 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 348 \{ 0 \; mod \; 6, 77 \; mod \; 6, 154 \; mod \; 6, 349 231 \; mod \; 6, 308 \; mod \; 6, 385 \; mod \; 6 \} 350 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 383 \label{eq:cpri0:ppn0:00a0} 384 ax + by = n 385 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 396 \label{eq:cpri0:ppn0:00a1} 397 n = \gcd(a,b) \left( { \frac{ax}{\gcd(a,b)} + \frac{by}{\gcd(a,b)} } \right) . 398 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 445 \label{eq:lem:cpri0:gcd0:01:01} 446 \gcd(a,b) = \gcd(a, b + a). 447 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