%$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 $ \chapter[\cprizeroshorttitle{}]{\cprizerolongtitle{}} \label{cpri0} \beginchapterquote{``The number of primes less than 1,000,000,000 is 50,847,478: this is enough for an engineer, and he can be perfectly happy without the rest.''} {G.H. Hardy \cite{bibref:b:mathematiciansapology:1940}, p. 102} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} %Section Tag INT0 \label{cpri0:int0} This chapter presents important properties of integers and prime numbers; and related topics and concepts. Nearly all of the ideas presented come from number theory (a branch of mathematics). Our aim in this chapter is to provide the reader with the background necessary to understand other topics in the work (Farey series, continued fractions, and rational approximation). Because this work is concerned with microcontroller software development (rather than mathematics), the treatment is regrettably minimal. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Sets Of Integers} %Section tag: SOI0 \label{cpri0:soi0} An\index{integer}\index{sets of integers}\index{integer!sets of} \emph{integer} is a positive or negative whole number, such as 0, $\pm$1, $\pm$2, $\pm$3, \ldots{} (\cite{bibref:b:penguindictionaryofmathematics:2ded}). The set of integers is denoted $\vworkintset$:\index{Z@$\vworkintset$}% \index{integer!Z@$\vworkintset$} \begin{equation} \vworkintset = \{ \ldots{} , -3, -2, -1, 0, 1, 2, 3, \ldots{} \}. \end{equation} A \emph{natural number}\index{natural number}\index{counting number} \index{integer!natural number}\index{integer!counting number} (or \emph{counting number}) is a positive integer, such as 1, 2, 3, \ldots{} (\cite{bibref:b:penguindictionaryofmathematics:2ded}). In this work, the set of natural numbers is denoted $\vworkintsetpos$:\index{N@$\vworkintsetpos$}\index{integer!N@$\vworkintsetpos$} \begin{equation} \vworkintsetpos = \{ 1, 2, 3, 4, 5, \ldots{} \}. \end{equation} A \emph{non-negative integer}\index{non-negative integer}\index{integer!non-negative} is an integer which is not negative, such as 0, 1, 2, 3, \ldots{}. In this work, the set of non-negative integers is denoted $\vworkintsetnonneg$:\footnote{This notation is somewhat unconventional, as in most works $\vworkintsetnonneg$ denotes the set of natural numbers; see \cite{bibref:b:penguindictionaryofmathematics:2ded}, p. 223.}\index{Z+@$\vworkintsetnonneg$}\index{integer!Z+@$\vworkintsetnonneg$} \begin{equation} \vworkintsetnonneg = \{ 0, 1, 2, 3, 4, \ldots{} \}. \end{equation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Divisibility Of Integers With No Remainder} \label{cpri0:doi0} We follow the convention of \cite{bibref:b:HardyAndWrightClassic} and use `$\vworkdivides$' \index{divides@divides ($\vworkdivides$)} \index{--@$\vworkdivides$ (divides)} to denote that one integer can divide another with no remainder, and use `$\vworknotdivides$' \index{divides@divides ($\vworkdivides$)} \index{--@$\vworknotdivides$ (doesn't divide)} to denote that one integer cannot divide another without a remainder. $a \vworkdivides b$, read ``$a$ divides $b$'', denotes that $b/a$ has no remainder; and $a \vworknotdivides b$, read ``$a$ does not divide $b$'', denotes that $b/a$ has a remainder. The following implications (\cite{bibref:b:HardyAndWrightClassic}, p. 1) are intuitively plain, and we accept them without proof. \begin{equation} b \vworkdivides a \wedge c \vworkdivides b \vworkhimp c \vworkdivides a \end{equation} \begin{equation} b \vworkdivides a \vworkhimp b c \vworkdivides a c \end{equation} \begin{equation} c \vworkdivides a \wedge c \vworkdivides b \vworkhimp c \vworkdivides (m a + n b) \end{equation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Prime Numbers And Composite Numbers} %Section tag: PNC0 \label{cpri0:pnc0} A \emph{prime number}\index{prime number} (or, more tersely, a \emph{prime}) is a natural number which has as its natural-number factors only 1 and itself. Any natural number which is not a prime is a product of primes, and is called a \emph{composite number}\index{composite number} (or just a \emph{composite}). The number `1' is considered neither prime nor composite. As examples, the first ten prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. The first ten composite numbers are $4 = 2 \times 2$, $6 = 2 \times 3$, $8 = 2 \times 2 \times 2$, $9 = 3 \times 3$, $10 = 2 \times 5$, $12 = 2 \times 2 \times 3$, $14 = 2 \times 7$, $15 = 3 \times 5$, $16 = 2 \times 2 \times 2 \times 2$, and $18 = 2 \times 3 \times 3$. Many properties of prime numbers were understood even prior to Euclid's time\footnote{Euclid's \emph{gcd($\cdot{},\cdot{}$)} algorithm, for example, dates back to at least 200 B.C.} ($\approx$200 B.C.), but many other properties were discovered relatively recently (1600 A.D. and later). In recent history, the difficulty of factoring large composite numbers into their [large] prime components has become a linchpin of cryptography. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Properties Of Prime Numbers} %Subsection Tag: PPN0 \label{cpri0:ppn0} This section presents several important properties of prime numbers. Most of our readers---presumably being in predominantly technical vocations---are probably familiar with most of these properties. Prime numbers are the fundamental currency of arithmetic---the fundamental atomic ``stuff'' from which all integers are constructed. The first properties presented involve this aspect of primes. The presentation and the presentation order in \cite{bibref:b:HardyAndWrightClassic} is perfect, so we don't deviate. \begin{vworktheoremstatement} \label{thm:cpri0:ppn0:00} Every positive integer, except 1, is a product of primes. \end{vworktheoremstatement} \begin{vworktheoremproof} See \cite{bibref:b:HardyAndWrightClassic}, p. 2. \end{vworktheoremproof} \vworktheoremfooter{} When a number is factored into its prime components, we follow \cite{bibref:b:HardyAndWrightClassic}, p. 2 in defining a standard (or canonical) form for such a factorization. Theorem \ref{thm:cpri0:ppn0:00} establishes that any integer, except 1, can be factored into prime components. Theorem \ref{thm:cpri0:ppn0:01} (The Fundamental Theorem Of Arithmetic), establishes a stronger result---that such a factorization is unique. \begin{equation} n = p_1^{a_1} p_2^{a_2} \ldots{} p_k^{a_k}; \; (a_1 > 0, a_2 > 0, \ldots{} , a_k > 0, p_1 < p_2 < \ldots{} < p_k) \end{equation} \begin{vworktheoremstatementpar}{The Fundamental Theorem Of Arithmetic} \label{thm:cpri0:ppn0:01} (\cite{bibref:b:HardyAndWrightClassic}, p. 3) The standard form of $n$ is unique; apart from the rearrangement of factors, $n$ can be expressed as a product of primes in one way only. \end{vworktheoremstatementpar} \begin{vworktheoremproof} See \cite{bibref:b:HardyAndWrightClassic}, p. 21. \end{vworktheoremproof} \vworktheoremfooter{} A \index{prime number!properties} reasonable question to ask is, is there a largest prime number? Or, equivalently, is there a limited supply of prime numbers? It is known that there is no largest prime number and that there is an infinite number of prime numbers. Euclid's famous proof that there is no largest prime number is reproduced below. \begin{vworktheoremstatementpar}{Euclid's Second Theorem} The number of primes is infinite.\index{Euclid}\index{Euclid!Second Theorem}% \index{prime number!no largest prime number} \end{vworktheoremstatementpar} \begin{vworktheoremproof} (\cite{bibref:b:HardyAndWrightClassic}, p.12) Assume there is a largest prime number, denoted $p$. Let $2 \times 3 \times 5 \times \ldots \times p$ be the aggregate (i.e. product) of primes up to $p$, and let \begin{equation} q = (2 \times 3 \times 5 \times \ldots{} \times p) + 1. \end{equation} $q$ is not divisible by any of the prime numbers $2, 3, 5, \ldots{}, p$. $q$ is therefore either prime, or divisible by a prime between $p$ and $q$. In either case there is a prime greater than $p$, which is a contradiction, and proves the theorem. \end{vworktheoremproof} %\vworktheoremfooter{} \begin{vworktheoremstatementpar}{Euclid's First Theorem} \index{Euclid}\index{Euclid!First Theorem}% If $p$ is prime and $p \vworkdivides{} a b$, then $p \vworkdivides{} a$ or $p \vworkdivides{} b$. \end{vworktheoremstatementpar} \begin{vworktheoremproof} Waiting on information for the proof. \end{vworktheoremproof} \begin{vworktheoremparsection}{Remarks} \begin{itemize} \item $p$ may divide both $a$ and $b$: ``or'' is used in the \emph{logical} sense. \item This theorem essentially says that the divisibility by a prime may not be ``split'' across the two factors $a$ and $b$ so as to obscure it; i.e. primes are the fundamental currency of arithmetic. \item Note that this statement is not true in general for a composite $p$. For example, let $p = 6$, $a = 10$, $b = 21$: $6 \vworkdivides{} 210$, but $6 \vworknotdivides{} 10$ and $6 \vworknotdivides{} 21$. \end{itemize} \end{vworktheoremparsection} %\vworktheoremfooter{} \begin{vworklemmastatement} \label{lem:cpri0:ppn0:000p} For $a, b, x, y \in \vworkintsetpos$, if \begin{equation} ax - by = 1 , \end{equation} then $a$ and $b$ are coprime. \end{vworklemmastatement} \begin{vworklemmaproof} Assume that $a$ and $b$ are \emph{not} coprime, i.e. that $\gcd(a,b) > 1$. Then \begin{equation} ax-by = \gcd(a,b) \left( { \frac{ax}{\gcd(a,b)}-\frac{by}{\gcd(a,b)}} \right) \neq 1 , \end{equation} since $\gcd(a,b) > 1$. \end{vworklemmaproof} %\vworklemmafooter{} \begin{vworklemmastatement} \label{lem:cpri0:ppn0:00a} The equation \begin{equation} ax + by = n \end{equation} (with $a,b \in \vworkintsetpos$) is soluble in integers $x,y \in \vworkintset$ for any $n \in \vworkintset$ iff $a$ and $b$ are coprime. \end{vworklemmastatement} \begin{vworklemmaproof} First, it will be shown that if $a$ and $b$ are coprime, any $n$ can be reached through some choice of $x,y \in \vworkintset$. (In fact, we give a procedure for choosing $x$ and $y$.) Form the set \begin{equation} \label{eq:cpri0:ppn0:00a00} \{ 0b \; mod \; a, 1b \; mod \; a, 2b \; mod \; a, \ldots{} , (a-2)b \; mod \; a, (a-1)b \; mod \; a \} . \end{equation} Note in this set that each integer $\{0, \ldots, a-1 \}$ is present exactly once, but not necessarily in order. To show that each integer $\{0, \ldots, a-1 \}$ is present exactly once, note that the set contains exactly $a$ elements, and note that each element is $\in \{0, \ldots, a-1 \}$. In order for each integer $\{0, \ldots, a-1 \}$ \emph{not} to be present exactly once, the set must contain at least one duplication of an element. Assume that a duplication exists, namely that $pb \; mod \; a = qb \; mod \; a$, for some $p$ and $q$ with $p \neq q$ and $0 \leq p,q \leq a-1$. In that case, we would have $(q-p) b = ka$. Because $a$ and $b$ are coprime (share no prime factors), this would require $(q-p)$ to have at least every prime factor in $a$ with at least the same multiplicity as $a$, which would imply that $(q-p) \geq a$, a contradiction. Thus, there are no duplicates in the set (\ref{eq:cpri0:ppn0:00a00}), and every integer $\{0, \ldots, a-1 \}$ is present. It is clear then that $x$ and $y$ can always be chosen by ``modulo shopping''. We could, for example, calculate $n \; mod \; a$, and find some $y$ s.t. $yb \; mod \; a = n \; mod \; a$, then choose $x$.\footnote{It is guaranteed that we \emph{can} find such an $x$ because the choice of $x$ moves $n$ in steps of $a$---thus by varying $x$ we can adjust $n$ to be \emph{any} integer s.t. $n \; mod \; a = yb \; mod \; a$, and this means that there is necessarily a choice for $x$ s.t. $ax+by=n$.} This technique is illustrated in Example \ref{ex:cpri0:ppn0:01}. If $a$ and $b$ are not coprime, this is equivalent to the statement that $\gcd(a,b) > 1$. The same argument as is present in Theorem \ref{thm:cpri0:ppn0:00a} and Equation \ref{eq:cpri0:ppn0:00a1} apply---only $n$ which are multiples of $\gcd(a,b)$ can be ``reached'', no matter what $x$ and $y$ are chosen. \end{vworklemmaproof} %\vworklemmafooter{} \begin{vworkexamplestatement} \label{ex:cpri0:ppn0:01} Find integers $x$ and $y$ such that \begin{equation} 6 x + 77 y = 731 \end{equation} \end{vworkexamplestatement} \begin{vworkexampleparsection}{Solution I (``Modulo Shopping'')} First, fix $y$ using the ``modulo shopping'' method suggested by Lemma \ref{lem:cpri0:ppn0:00a}. Building the set \begin{equation} \{ 0 \; mod \; 6, 77 \; mod \; 6, 154 \; mod \; 6, 231 \; mod \; 6, 308 \; mod \; 6, 385 \; mod \; 6 \} \end{equation} yields $\{ 0, 5, 4, 3, 2, 1 \}$. Note that $731 \; mod \; 6$ is 5, so we want to choose $y=1$ (corresponding to the second element in the sets above). With $y$ fixed at 1, any choice of $x$ will yield a result $6x + 77y$ such that $(6x + 77y) \; mod \; 6 = 5$. The solution of $6x + 77 = 731$ yields $x=109$. \end{vworkexampleparsection} \begin{vworkexampleparsection}{Solution II (Continued Fractions)} A second (and far more efficient) way to tackle this problem comes from the study of continued fractions (see \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0}, \emph{\ccfrzeroshorttitle{}}). If the continued fraction partial quotients and convergents of $a/b$ are calculated, it is guaranteed that the final convergent $p_k/q_k$ will be $a/b$ (because $a$ and $b$ are coprime), and the property of continued fraction convergents that $q_k p_{k-1} - p_k q_{k-1} = (-1)^k$ gives a way to choose $x, y$ s.t. $ax + by = 1$. With that $x,y$ known (call them $x'$ and $y'$), the equation can be scaled so that choosing $x=nx'$ and $y=ny'$ will result in a solution. This method is not illustrated here. The important point is that a solution can always be found. \end{vworkexampleparsection} %\vworkexamplefooter{} \begin{vworktheoremstatement} \label{thm:cpri0:ppn0:00a} For $a, b \in \vworkintsetpos$, the equation \begin{equation} \label{eq:cpri0:ppn0:00a0} ax + by = n \end{equation} has integer solutions $x,y \in \vworkintset$ iff $\gcd(a,b) \vworkdivides n$. \end{vworktheoremstatement} \begin{vworktheoremproof} First, note that choices of $x,y \in \vworkintset$ can result only in a linear combination of $a, b$ (the left-hand side of Eq. \ref{eq:cpri0:ppn0:00a0}) which is an integral multiple of $\gcd(a,b)$: \begin{equation} \label{eq:cpri0:ppn0:00a1} n = \gcd(a,b) \left( { \frac{ax}{\gcd(a,b)} + \frac{by}{\gcd(a,b)} } \right) . \end{equation} Note that $a/\gcd(a,b), b/\gcd(a,b) \in \vworkintsetpos$, and note also that $a/\gcd(a,b)$ and $b/\gcd(a,b)$ are by definition coprime. Lemma \ref{lem:cpri0:ppn0:00a} shows that the linear combination of two coprime natural numbers can form any integer. Thus, through suitable choices of $x$ and $y$, any integral multiple of $\gcd(a,b)$ can be formed. It has been shown that \emph{only} integral multiples of $\gcd(a,b)$ can be formed by choosing $x$ and $y$, and that \emph{any} integral multiple of $\gcd(a,b)$ can be formed by an appropriate choice of $x$ and $y$. Thus, if $\gcd(a,b) \vworknotdivides n$, $x$ and $y$ cannot be chosen to satisfy (\ref{eq:cpri0:ppn0:00a0}); but if $\gcd(a,b) \vworkdivides n$, $x$ and $y$ can always be chosen to satisfy (\ref{eq:cpri0:ppn0:00a0}). \end{vworktheoremproof} \vworktheoremfooter{} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The Greatest Common Divisor And Least Common Multiple} %Section tag: GCD0 \label{cpri0:gcd0} The \index{greatest common divisor}\index{GCD}greatest common divisor (or GCD) and \index{least common multiple}\index{LCM}least common multiple are integer-valued functions of integers to which most readers have had exposure during elementary school. We present these functions and several of their properties both as a review and to present properties that are not commonly used. \begin{vworkdefinitionstatementpar}{Greatest Common Divisor} \label{def:cpri0:gcd0:01} The \emph{greatest common divisor} of two positive integers $a$ and $b$, denoted $\gcd(a,b)$, is the largest integer that divides both $a$ and $b$. \end{vworkdefinitionstatementpar} \begin{vworklemmastatement} \label{lem:cpri0:gcd0:01} For $a,b \in \vworkintsetpos$, \begin{equation} \label{eq:lem:cpri0:gcd0:01:01} \gcd(a,b) = \gcd(a, b + a). \end{equation} \end{vworklemmastatement} \begin{vworklemmaproof} For an integer $g \in \vworkintsetpos$, if $g \vworkdivides a$ and $g \vworkdivides b$, then $g \vworkdivides (b+a)$. If $g \vworknotdivides b$ and $g \vworkdivides a$, then $g \vworknotdivides (b+a)$. Thus any integer $g$ which divides both $a$ and $b$ also divides both $a$ and $b+a$, and any integer which either does not divide $a$ or does not divide $b$ cannot divide both $a$ and $b+a$. The greatest common divisor of $a$ and $b$ is defined as the largest integer which divides both $a$ and $b$. Because of the relationship described above, the largest integer which divides both $a$ and $b$ is also the largest integer which divides both $a$ and $b+a$, proving (\ref{eq:lem:cpri0:gcd0:01:01}) and the lemma. \end{vworklemmaproof} \vworklemmafooter{} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Acknowledgements} %Section tag: ACK0 We would like to gratefully acknowledge the assistance of Iain Davidson\index{Davidson, Iain} \cite{bibref:i:iaindavidson}, G\'erard Nin\index{Nin, Gerard@Nin, G\'erard} \cite{bibref:i:gerardnin}, and Tim Robinson\index{Robinson, Tim} \cite{bibref:i:timrobinson} with Lemmas \ref{lem:cpri0:ppn0:000p} and \ref{lem:cpri0:ppn0:00a} and Example \ref{ex:cpri0:ppn0:01}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Exercises} %Section tag: EXE0 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent\begin{figure}[!b] \noindent\rule[-0.25in]{\textwidth}{1pt} \begin{tiny} \begin{verbatim} $RCSfile: c_pri0.tex,v $ $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_pri0/c_pri0.tex,v $ $Revision: 1.6 $ $Author: dtashley $ $Date: 2003/11/30 01:18:17 $ \end{verbatim} \end{tiny} \noindent\rule[0.25in]{\textwidth}{1pt} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % $Log: c_pri0.tex,v $ % Revision 1.6 2003/11/30 01:18:17 dtashley % Chapter modified to eliminate double horizontal lines. % % Revision 1.5 2003/04/03 19:49:36 dtashley % Global corrections to typeface of "gcd" made as per Jan-Hinnerk Reichert's % recommendation. % % Revision 1.4 2003/03/25 05:31:22 dtashley % Lemma about gcd()'s added, specifically that gcd(a,b)=gcd(a,b+a). % % Revision 1.3 2002/07/29 16:30:09 dtashley % Safety checkin before moving work back to WSU server Kalman. % % Revision 1.2 2001/07/01 19:32:06 dtashley % Move out of binary mode for use with CVS. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % $History: c_pri0.tex $ % % ***************** Version 10 ***************** % User: Dashley1 Date: 3/07/01 Time: 12:17a % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers % Edits. % % ***************** Version 9 ***************** % User: Dashley1 Date: 2/10/01 Time: 2:03a % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers % Completion of Farey series chapter. % % ***************** Version 8 ***************** % User: Dashley1 Date: 1/31/01 Time: 4:20p % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers % Edits. % % ***************** Version 7 ***************** % User: Dashley1 Date: 12/22/00 Time: 12:56a % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers % Tcl automated method of build refined. % % ***************** Version 6 ***************** % User: David T. Ashley Date: 8/12/00 Time: 9:48p % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers % Edits. % % ***************** Version 5 ***************** % User: David T. Ashley Date: 8/06/00 Time: 8:50a % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers % Work on Prime Number and Farey Series chapters. % % ***************** Version 4 ***************** % User: David T. Ashley Date: 7/30/00 Time: 8:22p % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers % Edits. % % ***************** Version 3 ***************** % User: David T. Ashley Date: 7/29/00 Time: 11:50p % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers % Edits, addition of solutions manual volume. % % ***************** Version 2 ***************** % User: David T. Ashley Date: 7/09/00 Time: 11:23p % Updated in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers % Addition of new chapters, enhancements to preface. % % ***************** Version 1 ***************** % User: David T. Ashley Date: 7/09/00 Time: 9:24p % Created in $/uC Software Multi-Volume Book (A)/Chapter, PRI0, Prime Numbers % Initial check-in. %End of file C_PRI0.TEX