aUse strong induction to prove B ezouts identity for any a a

a)Use (strong) induction to prove B ezout’s identity: for any a and b, there exists integers s and t such that gcd(a, b) = sa + tb. Hint: use the inductive hypothesis to write gcd(b, r) = sb + tr.

(b) Based on your proof , find s and t such that 3 = s · 264 + t · 105. Showyourwork.

(c) Two numbers a and m are said to be relatively prime if they share no common factors, i.e. if gcd(a, m) = 1. Show that if a and m are relatively prime, then a has an inverse mod m. That is, there exists some b such that ab 1 mod m. Hint: use part (a).

Solution

Euclidean Algorithm. Euclidean Algorithm. Suppose a and b are integers with a b > 0. (1) Apply the division algorithm: a = bq + r, 0 r < b. (2) Rename b as a and r as b and repeat until r = 0. The last nonzero remainder is the greatest common divisor of a and b. The Euclidean Algorithm depends upon the following lemma. Lemma 2.1.1. If a = bq + r, then GCD(a, b) = GCD(b, r). Proof. We will show that if a = bq + r, then an integer d is a common divisor of a and b if, and only if, d is a common divisor of b and r. Let d be a common divisor of a and b. Then d|a and d|b. Thus d|(a bq), which means d|r, since r = a bq. Thus d is a common divisor of b and r. Now suppose d is a common divisor of b and r. Then d|b and d|r. Thus d|(bq +r), so d|a. Therefore, d must be a common divisor of a and b. Thus, the set of common divisors of a and b are the same as the set of common divisors of b and r. It follows that d is the greatest common divisor of a and b if and only if d is the greatest common divisor of b and r. Discussion The fact that the Euclidean algorithm actually gives the greatest common divisor of two integers follows from the division algorithm and the equality in Lemma 2.1.1. Applying the division algorithm repeatedly as indicated yields a sequence of remainders r1 > r2 > · · · > rn > 0 = rn+1, where r1 < b. Lemma 2.1.1 says that GCD(a, b) = GCD(b, r1) = GCD(r1, r2) = · · · = GCD(rn1, rn). But, since rn+1 = 0, rn divides rn1, so that GCD(rn1, rn) = rn. Thus, the last nonzero remainder is the greatest common divisor of a and b. Example 2.1.1. Find GCD (1317, 56). 2. INTEGERS AND ALGORITHMS 156 1317 = 56(23) + 29 56 = 29(1) + 27 29 = 27(1) + 2 27 = 2(13) + 1 2 = 1(2) + 0 GCD (1317,56)=1 Example 2.1.1 shows how to apply the Euclidean algorithm. Notice that when you proceed from one step to the next you make the new dividend the old divisor (replace a with b) and the new divisor becomes the old remainder (replace b with r). Recall that you can find the quotient q by dividing b into a on your calculator and rounding down to the nearest integer. (That is, q = ba/bc.) You can then solve for r. Alternatively, if your calculator has a mod operation, then r = mod(a, b) and q = (a r)/b. Since you only need to know the remainders to find the greatest common divisor, you can proceed to find them recursively as follows: Basis. r1 = a mod b, r2 = b mod r1. Recursion. rk+1 = rk1 mod rk, for k 2. (Continue until rn+1 = 0 for some n. ) 2.2. GCD’s and Linear Combinations. Theorem 2.2.1. If d = GCD(a, b), then there are integers s and t such that d = as + bt. Moreover, d is the smallest positive integer that can be expressed this way. Discussion Theorem 2.2.1 gives one of the most useful characterizations of the greatest common divisor of two integers. Given integers a and b, the expression as + bt, where s and t are also integers, is called a linear combination of a and b. Exercise 2.2.1. Prove that if a, b, s, t, and d are integers such that d|a and d|b, then d|(as + bt). The Euclidean Algorithm can, in fact, be used to provide the representation of the greatest common divisor of a and b as a linear combination of a and b. Here is how it would work for the example in Example 2.1.1. 2. INTEGERS AND ALGORITHMS 157 Example 2.2.1. Express 1 = GCD(1317, 56) as a linear combination of 1317 and 56. Solution: We work backwards using the equations derived by applying the Euclidean algorithm in example 2.1.1, expressing each remainder as a linear combination of the associated divisor and dividend: 1 = 27 13 · 2 linear combination of 2 and 27 1 = 27 13(29 27 · 1) substitute 2 = 29 27(1) 1 = 14 · 27 13 · 29 linear combination of 27 and 29 1 = 14(56 1 · 29) 13 · 29 substitute 27 = 56 1 · 29 1 = 14 · 56 27 · 29 linear combination of 29 and 56 1 = 14 · 56 27(1317 23 · 56) substitute 29 = 1317 23 · 56 1 = 635 · 56 27 · 1317 linear combination of 56 and 1317 (The dividends, divisors, and remainders have been underlined.) So GCD(1317, 56) = 1 = 1317(27) + 56(635).