1 |
dashley |
140 |
%$Header$ |
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 |