trunk/c_pri0/c_pri0.tex

%$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