THE EUCLIDEAN

ALGORITHM

Greatest Common Divisor:

A positive integer d is called a common divisor of the

integers a and b, if d divides a and b. The greatest possible such d is called

the greatest common divisor of a and b, denoted gcd(a,b).If = 1 gcd(a,b) then

a,b are called relatively prime.

The Euclidean Algorithm For Finding GCD:

EUCLID(a,b)

1.

If

b==0

2.

Return

a

3.

Else

return EUCLID(b,a mod b)

As an example of the running of

EUCLID, consider the computation of gcd(30,21)

EUCLID(30,21)= EUCLID(21,9)

= EUCLID(9,3)

= EUCLID(3,0)

=3

This computation calls EUCLID recursively three times.

The algorithm returns a in line 2, if b = 0, so that equation

(31.9) implies that gcd(a,b) = gcd.(a,0) = a. The algorithm cannot recurse

inde?nitely, since the second argument strictly decreases in each recursive

call and is always non negative. Therefore, EUCLID always terminates with the

correct answer.

Running Time Analysis of Euclid’s

Algorithm:

We analyze the worst-case running time of EUCLID as a

function of the size of a and b. We assume with no loss of generality that

a>b>= 0. To justify this assumption, observe that if b>a>= 0, then

EUCLID(a,b) immediately makes the recursive call EUCLID(b,a). That is, if the

?rst argument is less than the second argument, EUCLID spends one recursive

call swapping its arguments and then proceeds. Similarly, if b = a>0, the

procedure terminates after one recursive call, since a mod b =0.

The overall running

time of EUCLID is proportional to the number of recursive calls it makes.

The Extended Euclidean Algorithm For Finding GCD:

We extend the algorithm to compute the integer coef?cients x

and y such that

d =gcd(a,b)= ax +by

EXTENDED-EUCLID.(a,b)

1.

If

b==0

2.

Return(a,1,0)

3.

else

(d’,x’,y’)=EXTENDED-EUCLID(b,a mod b)

4.

(d,x,y)=(d’,x’,y’-a/by’)

5.

return(d,x,y)

The EXTENDED-EUCLID procedure is a

variation of the EUCLID procedure. Line 1 is equivalent to the condition in

SIMPLE EUCLIDEAN b == 0 in line 1 of EUCLID. If b = 0, then EXTENDED-EUCLID

returns not only d=a in line 2 but also the coefficients x=1 and y=0 so that

a=ax+by.If b not equal to zero, EXTENDED-EUCLID first computes(d’,x’,y’) such

that d’=gcd(b,a mod b) and d’=bx’+(b,a mod b).

Since the number of recursive calls

made in EUCLID is equal to the number of recursive calls made in

EXTENDED-EUCLID, the running times of EUCLID and EXTENDED-EUCLID are the same,

to within a constant factor. That is, for a>b>0, the number of recursive

calls is O.lgb