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:
return EUCLID(b,a mod b)
As an example of the running of
EUCLID, consider the computation of gcd(30,21)
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
Running Time Analysis of Euclid’s
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
(d’,x’,y’)=EXTENDED-EUCLID(b,a mod b)
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