Institut for Matematik og Datalogi Odense Universitet February 19, 1996

JFB

DM11 – F96 – Lecture 3

Lecture, February 14

We finished discussing cardinality, from section 1.7. Then, we covered section 2.3, and began on sections 2.4 and 2.5 (See the attached notes on the Extended Euclidean Algorithm.)

Lecture, February 21

We will finish sections 2.4 and 2.5 and possibly begin on chapter 3. We will skip the subsections of section 2.4 which deal with the representation of integers and the algorithms for integer operations, since this is covered in other courses.

Lecture, February 28

We will cover sections 3.1 and 3.2 in the text.

Problems to be discussed in week 9

5, 6, 13, 21, 22, 23, and 33 from section 2.3. 2b, 2d, 7, 10, 15, and 16 from section 2.5.

The Extended Euclidean Algorithm

This is a supplement to the textbook’s method for finding the integers s and t such that gcd(a, b) = sa + tb. Thm. a, b ∈ IN. There exist s, t ∈ ZZ s.t. sa + tb = gcd(a, b). Pf. Let d be the smallest positive integer in D = {xa + yb | x, y ∈ ZZ}. d ∈ D ⇒ d = x′a + y′b for some x′, y′ ∈ ZZ. Now, gcd(a, b)|a and gcd(a, b)|b, so gcd(a, b)|x′a, gcd(a, b)|y′b, and gcd(a, b)|(x′a + y′b) = d. Now, we will show that d|gcd(a, b), so d = gcd(a, b). Note a ∈ D, since a = 1 · a + 0 · b, so 0 < d ≤ a. Suppose a = dq + r with 0 ≤ r < d.

r = a − dq
= a − q(x′a + y′b)
= (1 − qx′)a − (qy′)b

⇒ r ∈ D r < d ⇒ r = 0 ⇒ d|a. Similarly, one can show that d|b. Therefore, d|gcd(a, b). □ How do you find d, s and t? Let d = gcd(a, b). Write b as b = aq + r with 0 ≤ r < d. Then, d|b ⇒ d|(aq + r). Also, d|a ⇒ d|(aq) ⇒ d|((aq + r) − aq) ⇒ d|r.

Let d′ = gcd(a, b − aq). Then, d′|a ⇒ d′|(aq) Also, d′|(b − aq) ⇒ d′|((b − aq) + aq) ⇒ d′|b.

Thus, gcd(a, b) = gcd(a, b (mod a)) = gcd(b (mod a), b). Thus, if we start out with two large numbers for which we want to find the greatest common divisor, we have a method for reducing to a problem where we have reduced the size of one of the numbers. This is the idea behind the Euclidean algorithm for finding the gcd. While executing the Euclidean algorithm, we can keep track of some of the quotients we compute and use them to calculate the s and t we want. This gives us the Extended Euclidean Algorithm:

{ Initialize}

d_{0} ← b  s_{0} ← 0  t_{0} ← 1
d_{1} ← a  s_{1} ← 1  t_{1} ← 0
n ← 1

{ Compute next d} while d_{n} > 0 do

begin

n ← n + 1
q_{n} ← ⌊d_{n−2}/d_{n−1}⌋

d_{n} ← d_{n−2} − q_{n}d_{n−1} { d_{n−2} (mod d_{n−1})}

s_{n} ← q_{n}s_{n−1} + s_{n−2}
t_{n} ← q_{n}t_{n−1} + t_{n−2}

end s ← (−1)^{n}s_{n−1} t ← (−1)^{n−1}t_{n−1} gcd(a, b) ← d_{n−1}

Note that ⌊x⌋ is the floor function, also called the greatest integer function, defined on page 68 of the textbook. It is simply truncation, and in this case it gives the result of an integer division. The proof of correctness is by induction and the analysis of the running time uses Fibonacci numbers. We get to this later in the course. How can we find multiplicative inverses modulo m? Given a and m, we want to find x such that a · x = 1 (mod m). This means we also want a k, so it all satisfies ax = 1+km. Thus, we want to solve for an s in an equation sq +tm = 1. This can be done if a and m are relatively prime. Just use the Extended Euclidean algorithm.