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