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