Parent Directory | Revision Log

Revision **6** -
(**show annotations**)
(**download**)
(**as text**)

*Fri Oct 7 01:36:46 2016 UTC*
(7 years, 9 months ago)
by *dashley*

File MIME type: application/x-tex

File size: 23315 byte(s)

File MIME type: application/x-tex

File size: 23315 byte(s)

Initial commit after migrating from CVS.

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

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 |

dashley@gmail.com | ViewVC Help |

Powered by ViewVC 1.1.25 |