1: [5] Let a, b be positive integers with god(a, b) = 1. (a) [2] Prove that ab - a - b cannot be written as ar + by where r, y are non-negative integers. (b) [3] Prove that for any integer n > ab - a - b, there exist non-negative integers r, y such that n = ar+ by. Hint: The best chance for a solution is to take a to be as small as possible and hope that the corresponding y is non-negative. 2: [5] Let Zo denote the set of non-negative integers. Let f : Z20 X Z20 -> Zzo be a function such that f(b, a) = f(a, b) = f(b - a, a) for any integers 0 n, then > > n 2 no; if r s n, then r E T and so r 2 no. Therefore, no is the smallest element of S. O Corollary 1.3 The set NU {0} is well-ordered. Corollary 1.4 (Induction) For any n E N, let P(n) be a statement such that the following are true: 1. P(1) is true, 2. (P(1) A . . . AP(n - 1)) = P(n) is true for all integers n 2 2. Then P(n) is true for all n e N. Proof: Let S be the set of natural numbers n such that P(n) is false. If S is empty, then we are done. Suppose for a contradiction that S is non-empty. Let me S be its smallest element. Since P(1) is true, we know that m # 1 and so m 2 2. Since m is the smallest element of S, we know that P(1), .... P(m -1) are all true, but then by property 2, we have P(m) is true. Contradiction. O Remark: There are variant forms where multiple base cases are needed or where the starting point is > 1. Proposition 1.5 (Division algorithm) Let a, b be integers such that a > 0. Then there exists integers q, r such that b = aq +r, Ogr ca. Proof: Consider the set S = {b - ak: ke Z, b - ak 2 0}. By taking k = -|b), we have since a 2 1, b - ka = b + |bla >b+ 16/ 20.Hence S C NU {0} is non-empty. Let re S be its smallest element. Then r = b - ak for some ke Z and 7 2 0. Let q = k so that b = aq + r. It remains to prove that r 0}. If a > 0, then a = a(1) e S. If a 0. Now r = c-dq = ar, + by1 - (aro + byo)q = a(21 - cog) + b(y1 - 309). Since r > 0, we have re S, but this contradicts the minimality of d. O Lemma 1.7 Any common divisor of a, b divides d. In other words, d = god(a, b) is the greatest common divisor of a and b. Proof: If e | a and e | b, then e | aro + byo. So el d. O We define ged(0, 0) = 0 so that god(0, a) = lal for any n E Z. Corollary 1.8 (Bezout's Lemma) Let a, b be integers. Then there exist integers c, y such that god(a, b) = or + by