Institut for Matematik og Datalogi Odense Universitet February 26, 1996

JFB

DM11 – F96 – Lecture 4

Lecture, February 21

We finished section 2.4 and most of section 2.5. We skipped the subsections of section 2.4 which deal with the representation of integers and the algorithms for integer operations.

Lecture, February 28

We will finish section 2.5 and cover sections 3.1 and 3.2 in the text. We are skipping section 2.6, since it is covered in other courses.

Lecture, March 6

We will cover section 3.3 and structural induction.

Announcement 1

Per Vikkelsøe’s discussion section which would have been held on Thursday, February 29, will instead be held on Tuesday, March 5, from 8 to 10 AM in the seminar room. Anders Yeo’s section will be held where it usually is, but it is full, so students in Per’s section are advised to go to the section on March 5 if they can.

Announcement 2

In both discussion sections next week (February 29 and March 5), the problems from the second weekly note (those which you began discussing on February 22) will be discussed further. It appears that there were too many problems to be done in one discussion section, so if you have not finished doing those which were not yet done in your discussion section, look at them again.

Problems to be discussed in week 10

18, 23, 31 from section 2.5. (Note: 31 is not easy, but try doing it yourself before looking up the answer.) 3, 4, 20, 30 from section 3.1. 6, 25, 26, 28, 33, 36, 40, 44, 50 from section 3.2. You may turn in number 28 to your instructor for comments. Problem 50 from section 3.2 is a little challenging.

Proof of correctness of the Extended Euclidean Algorithm

It is easiest to first show that the greatest common divisor is itself computed correctly and then show that the values s and t are correct. These two steps toward proving the correctness each use a claim which is proven by induction. Claim: gcd(a, b) = gcd(d_{k}, d_{k−1}) for 1 ≤ k ≤ n. Pf. (by induction on k) Basis step: k = 1. d_{1} = a, d_{0} = b, so gcd(a, b) = gcd(d_{1}, d_{1−1}). √ Inductive step: Assume that gcd(a, b) = gcd(d_{k}, d_{k−1}) and 1 ≤ k ≤ n − 1. Then d_{k+1} = d_{k−1} −q_{k+1}d_{k}, so, as argued before, gcd(d_{k}, d_{k−1}) = gcd(d_{k+1}, d_{k}). By the inductive hypothesis, this is equal to gcd(a, b). √ Thus, gcd(a, b) = gcd(d_{k}, d_{k−1}) for 1 ≤ k ≤ n. □ Since d_{n} = 0, gcd(d_{n}, d_{n−1}) = d_{n−1}, which is the result produced by the algorithm. By the previous claim, this is the correct greatest common divisor. Claim: (−1)^{k−1}s_{k}a + (−1)^{k}t_{k}b = d_{k} for 0 ≤ k ≤ n − 1. Pf. (by induction on k) Basis step: k = 0. d_{0} = b, s_{0} = 0, and t_{0} = 1, so (−1) · 0 · a + (1) · 1 · b = d_{0}. √ k = 1. d_{1} = a, s_{1} = 1, and t_{1} = 0, so (1) · 1 · a + (−1) · 0 · b = d_{1}. √ Inductive step: Assume (−1)^{k−1}s_{k}a+(−1)^{k}t_{k}b = d_{k} for 0 ≤ k < k′, where 2 ≤ k′ ≤ n−1.

d_{k′} = d_{k′−2} − q_{k′}d_{k′−1}
= ((−1)^{k′−3}s_{k′−2}a + (−1)^{k′−2}t_{k′−2}b) − q_{k′}((−1)^{k′−2}s_{k′−1}a + (−1)^{k′−1}t_{k′−1}b)
= (−1)^{k′−1}(s_{k′−2} + q_{k′}s_{k′−1})a + (−1)^{k′}(t_{k′−2} + q_{k′}t_{k′−1})b
= (−1)^{k′−1}s_{k′}a + (−1)^{k′}t_{k′}b √

Thus, (−1)^{k−1}s_{k}a + (−1)^{k}t_{k}b = d_{k} for 0 ≤ k ≤ n − 1. □

Since the algorithm sets s = (−1)^{n}s_{n−1} and t = (−1)^{n−1}t_{n−1}, the final values satisfy sa + tb = d_{n−1} = gcd(a, b). Thus, the algorithm is correct.