Answer to Question #270954 in Discrete Mathematics for atty

Question

The recursive algorithm given below can be used to compute gcd(a, b) where a

and b are non-negative integer, not both zero.

procedure gcd(a, b)

if a > b then gcd(a, b) := gcd(b, a)

else if a = 0 then gcd(a, b) := b

else if a = 1 then gcd(a, b) := 1

else if a and b are even then gcd(a, b) := 2gcd(a/2, b/2)

else if a is odd and b is even then gcd(a, b) := gcd(a, b/2)

else gcd(a, b) := gcd(a, b − a)

Use this algorithm to compute

(a) gcd(124, 244) (b) gcd(4424, 2111).

Answer 1

(a)gcd(124, 244)=2*gcd(62,122)=4*gcd(31,61)=4*gcd(31,30)=4*gcd(30,31)=4*gcd(30,1)=4*gcd(1,30)=

=4*1=4

(b)gcd(4424,2111)=gcd(2111,4424)=gcd(2111,2212)=gcd(2111,1106)=gcd(1106,2111)=

=gcd(1106,1005)=gcd(1005,1106)=gcd(1005,553)=gcd(553,1005)=gcd(553,452)=gcd(452,553)=

=gcd(452,101)=gcd(101,452)=gcd(101,226)=gcd(101,113)=gcd(101,12)=gcd(12,101)=gcd(12,89)=

=gcd(12,77)=gcd(12,65)=gcd(12,53)=gcd(12,41)=gcd(12,29)=gcd(12,17)=gcd(12,5)=gcd(5,12)=

=gcd(5,6)=gcd(5,1)=gcd(1,5)=1