THE EUCLIDEANALGORITHMGreatest Common Divisor:A positive integer d is called a common divisor of theintegers a and b, if d divides a and b. The greatest possible such d is calledthe greatest common divisor of a and b, denoted gcd(a,b).If = 1 gcd(a,b) thena,b are called relatively prime.The Euclidean Algorithm For Finding GCD:EUCLID(a,b)1. Ifb==02. Returna3.
Elsereturn EUCLID(b,a mod b)As an example of the running ofEUCLID, consider the computation of gcd(30,21)EUCLID(30,21)= EUCLID(21,9)= EUCLID(9,3)= EUCLID(3,0)=3This 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 recurseinde?nitely, since the second argument strictly decreases in each recursivecall and is always non negative. Therefore, EUCLID always terminates with thecorrect answer.Running Time Analysis of Euclid’sAlgorithm:We analyze the worst-case running time of EUCLID as afunction of the size of a and b.
We assume with no loss of generality thata>b>= 0. To justify this assumption, observe that if b>a>= 0, thenEUCLID(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 recursivecall 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 runningtime 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 xand y such thatd =gcd(a,b)= ax +byEXTENDED-EUCLID.(a,b)1. Ifb==02.
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 avariation of the EUCLID procedure. Line 1 is equivalent to the condition inSIMPLE EUCLIDEAN b == 0 in line 1 of EUCLID.
If b = 0, then EXTENDED-EUCLIDreturns not only d=a in line 2 but also the coefficients x=1 and y=0 so thata=ax+by.If b not equal to zero, EXTENDED-EUCLID first computes(d’,x’,y’) suchthat d’=gcd(b,a mod b) and d’=bx’+(b,a mod b).Since the number of recursive callsmade in EUCLID is equal to the number of recursive calls made inEXTENDED-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 recursivecalls is O.lgb