The Art and Craft of Problem Solving

224 CHAPTER 7 NUMBER THEORY in other words, 60 has two completely different E-prime factorizations, and consequently, if x,y E E ...

7.1 PRIMES AND DIVISIBILITY 225 Let a and b be positive integers, b 2 a. Then there exist integers q, r satis­ fying q 2 1 and 0 ...

226 CHAPTER 7 NUMBER THEORY Then there exist integers x, y such that px + ay = 1. Now we need to use the hypothesis that plab. L ...

1 PRIMES AND DIVISIBILITY 227 Since the right-hand side is a multiple of v, and v shares no factor with un, we must conclude t ...

228 CHAPTER 7 NUMBER THEORY Problems and Exercises 7.1. 9 Write out a formal proof of the FfA. 7.1.10 Review Example 3.2.4 on pa ...

(e) Likewise, show that 2 - Rand 2 + R are F-primes. (f) Conclude that F does not possess unique factor­ ization. 7.1.15 Prove t ...

230 CHAPTER 7 NUMBER THEORY 7.2 Congruence Congruence notation was introduced on page 44. Recall that if a - b is a mUltiple of ...

7.2 CONGRUENCE 231 We are not going to prove this; Fermat's Last Theorem was perhaps the most famous outstanding problem in all ...

232 CHAPTER 7 NUMBER THEORY Fermat's Little Theorem Let's derive a nice consequence of (1). Let p be a prime and let a ..1 p. Si ...

7.2 CONGRUENCE 233 So indeed, ak+ 4 will be a multiple of 5. It seems that we can generate composite num­ bers in this sequence ...

234 CHAPTER 7 NUMBER THEORY called the digital sum of n. (b) Prove that the digital sum of the product of any two twin primes, o ...

7.3 NUMBER THEORETIC FUNCTIONS 235 7.3 Number Theoretic Functions Of the infinitely many functions with domain N, we will single ...

236 CHAPTER 7 NUMBER THEORY 7.3.6 An Important Counting Principle. Let n = ab, where a ..1 b. Show that if din then d = uv, wher ...

7.3 NUMBER THEORETIC FUNCTIONS 237 since any number that shares a factor with 12 will be a mUltiple of either 2 or 3 (or both). ...

238 CHAPTER 7 NUMBER THEORY and this makes sense; for we could argue that half of the positive integers up to 360 are odd, and t ...

7.3. 18 Find n E N such that J.l(n) + J.l(n + I) + J.l(n + 2) = 3. 7.3.19 Show that for all n,r E N, Gr (n) r ---n G-r(n) - . 7. ...

240 CHAPTER 7 NUMBER THEORY 7.3.30 The above equation used an arbitrary func­ tion g. If we replace g with /1, we can use some s ...

7.4 DIOPHANTINE EQUATIONS 241 Here is a simple example of a problem with a "complete" solution, illustrating one of the most imp ...

242 CHAPTER 7 NUMBER THEORY Example 7.4.2 Find all solutions to the diophantine equation x^2 + y^2 = 1000003. Solution: Consider ...

7.4 DIOPHANTINE EQUATIONS 243 On the other hand, it is true that if v .l w and u^2 = VW, then v and W must be perfect squares (t ...