Parent Directory | Revision Log

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

*Fri Oct 7 01:36:46 2016 UTC*
(6 years, 3 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 | 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 |

dashley@gmail.com | ViewVC Help |

Powered by ViewVC 1.1.25 |