output d

Show that this algorithm correctly computes gcd(a, b), and runs in time

O( 2 ), where := max(len(a), len(b)).

4.2 The extended Euclidean algorithm

Let a and b be non-negative integers, and let d := gcd(a, b). We know by

Theorem 1.6 that there exist integers s and t such that as + bt = d. The

extended Euclidean algorithm allows us to e¬ciently compute s and t.

The following theorem describes the algorithm, and also states a number

of important facts about the relative sizes of the numbers that arise during

the computation ” these size estimates will play a crucial role, both in the

analysis of the running time of the algorithm, as well as in applications of

the algorithm that we will discuss later.

Theorem 4.3. Let a, b, r0 , r1 , . . . , r +1 and q1 , . . . , q be as in Theorem 4.1.

De¬ne integers s0 , s1 , . . . , s +1 and t0 , t1 , . . . , t +1 as follows:

s0 := 1, t0 := 0,

s1 := 0, t1 := 1,

and for i = 1, . . . , ,

si+1 := si’1 ’ si qi , ti+1 := ti’1 ’ ti qi .

Then

(i) for i = 0, . . . , + 1, we have si a + ti b = ri ; in particular, s a + t b =

gcd(a, b);

(ii) for i = 0, . . . , , we have si ti+1 ’ ti si+1 = (’1)i ;

(iii) for i = 0, . . . , + 1, we have gcd(si , ti ) = 1;

(iv) for i = 0, . . . , , we have ti ti+1 ¤ 0 and |ti | ¤ |ti+1 |; for i = 1, . . . , ,

we have si si+1 ¤ 0 and |si | ¤ |si+1 |;

(v) for i = 1, . . . , + 1, we have ri’1 |ti | ¤ a and ri’1 |si | ¤ b.

4.2 The extended Euclidean algorithm 59

Proof. (i) is easily proved by induction on i. For i = 0, 1, the statement is

clear. For i = 2, . . . , + 1, we have

si a + ti b = (si’2 ’ si’1 qi’1 )a + (ti’2 ’ ti’1 qi’1 )b

= (si’2 a + ti’2 b) ’ (si’1 a + ti’1 b)qi

= ri’2 ’ ri’1 qi’1 (by induction)

= ri .

(ii) is also easily proved by induction on i. For i = 0, the statement is

clear. For i = 1, . . . , , we have

si ti+1 ’ ti si+1 = si (ti’1 ’ ti qi ) ’ ti (si’1 ’ si qi )

= ’(si’1 ti ’ ti’1 si ) (after expanding and simplifying)

= ’(’1)i’1 = (’1)i (by induction).

(iii) follows directly from (ii).

For (iv), one can easily prove both statements by induction on i. The

statement involving the ti is clearly true for i = 0; for i = 1, . . . , , we have

ti+1 = ti’1 ’ ti qi , and since by the induction hypothesis ti’1 and ti have

opposite signs and |ti | ≥ |ti’1 |, it follows that |ti+1 | = |ti’1 | + |ti |qi ≥ |ti |,

and that the sign of ti+1 is the opposite of that of ti . The proof of the

statement involving the si is the same, except that we start the induction

at i = 1.

For (v), one considers the two equations:

si’1 a + ti’1 b = ri’1 ,

si a + ti b = ri .

Subtracting ti’1 times the second equation from ti times the ¬rst, applying

(ii), and using the fact that ti and ti’1 have opposite sign, we obtain

a = |ti ri’1 ’ ti’1 ri | ≥ |ti |ri’1 ,

from which the inequality involving ti follows. The inequality involving si

follows similarly, subtracting si’1 times the second equation from si times

the ¬rst. 2

Suppose that a > 0 in the above theorem. Then for i = 1, . . . , + 1, the

value ri’1 is a positive integer, and so part (v) of the theorem implies that

|ti | ¤ a/ri’1 ¤ a and |si | ¤ b/ri’1 ¤ b. Moreover, if a > 1 and b > 0, then

> 0 and r ’1 ≥ 2, and hence |t | ¤ a/2 and |s | ¤ b/2.

Example 4.2. We continue with Example 4.1. The numbers si and ti are

easily computed from the qi :

60 Euclid™s algorithm

i 0 1 2 3 4

ri 100 35 30 5 0

qi 2 1 6

si 1 0 1 -1 7

ti 0 1 -2 3 -20

So we have gcd(a, b) = 5 = ’a + 3b. 2

We can easily turn the scheme described in Theorem 4.3 into a simple

algorithm, taking as input integers a, b, such that a ≥ b ≥ 0, and producing

as output integers d, s, and t, such that d = gcd(a, b) and as + bt = d:

r ← a, r ← b

s ← 1, s ← 0

t ← 0, t ← 1

while r = 0 do

q ← r/r , r ← r mod r

(r, s, t, r , s , t ) ← (r , s , t , r , s ’ s q, t ’ t q)

d←r

output d, s, t

Theorem 4.4. The extended Euclidean algorithm runs in time

O(len(a) len(b)).

Proof. We may assume that b > 0. It su¬ces to analyze the cost of comput-

ing the sequences {si } and {ti }. Consider ¬rst the cost of computing all of

the ti , which is O(„ ), where „ := i=1 len(ti ) len(qi ). We have t1 = 1 and,

by part (v) of Theorem 4.3, we have |ti | ¤ a for i = 2, . . . , . Arguing as in

the proof of Theorem 4.2, we have

„ ¤ len(q1 ) + len(a) len(qi ) ¤ len(q1 ) + len(a)( ’ 1 + log2 ( qi ))

i=2 i=2

= O(len(a) len(b)),

where we have used the fact that i=2 qi ¤ b. An analogous argument shows

that one can also compute all of the si in time O(len(a) len(b)), and in fact,

in time O(len(b)2 ). 2

Another, instructive way to view Theorem 4.3 is as follows. For i =

1, . . . , , we have

ri 01 ri’1

= .

1 ’qi

ri+1 ri

4.2 The extended Euclidean algorithm 61

Recursively expanding the right-hand side of this equation, we have for

i = 0, . . . , ,

ri a

= Mi ,

ri+1 b

where for i = 1, . . . , , the matrix Mi is de¬ned as

01 01

···

Mi := .

1 ’qi 1 ’q1

If we de¬ne M0 to be the 2 — 2 identity matrix, then it is easy to see that

si ti

Mi = ,

si+1 ti+1

for i = 0, . . . , . From this observation, part (i) of Theorem 4.3 is immediate,

and part (ii) follows from the fact that Mi is the product of i matrices, each

of determinant ’1, and the determinant of Mi is evidently si ti+1 ’ ti si+1 .

Exercise 4.2. One can extend the binary gcd algorithm discussed in Ex-

ercise 4.1 so that in addition to computing d = gcd(a, b), it also computes s

and t such that as + bt = d. Here is one way to do this (again, we assume

that a and b are positive integers):

r ← a, r ← b, e ← 0

while 2 | r and 2 | r do r ← r/2, r ← r /2, e ← e + 1

a ← r, ˜ ← r , s ← 1, t ← 0, s ← 0, t ← 1

˜ b

repeat

while 2 | r do

r ← r/2

if 2 | s and 2 | t then s ← s/2, t ← t/2

else s ← (s + ˜ b)/2, t ← (t ’ a)/2

˜

while 2 | r do

r ← r /2

if 2 | s and 2 | t then s ← s /2, t ← t /2

else s ← (s + ˜ b)/2, t ← (t ’ a)/2

˜

if r < r then (r, s, t, r , s , t ) ← (r , s , t , r, s, t)

r ← r ’ r, s ← s ’ s, t ← t ’ t

until r = 0

d ← 2e · r, output d, s, t