Recall that the greatest common divisor of two integers a and b, GCD(a, b), not both of which are zero, is the largest positive integer that divides both a and b. The Euclidean algorithm for finding this greatest common divisor of a and b is as follows:
- Divide a by b to obtain the integer quotient q and remainder r so that a = bq + r. Note: if b = 0, then GCD(a, b) = a.
- Now, GCD(a, b) = GCD(b, r) so replace a with b and b with r, and repeat this procedure
Since the remainders are decreasing, eventually a remainder of 0 will result. The last nonzero remainder is GCD(a, b). For example,
1260 = 198 x 6 + 72 GCD(1260,198) = GCD(198,72)
199 = 72 x 2 + 54 GCD(1260,198) = GCD(72,52)
72 = 54 x 1 + 18 GCD(1260,198) = GCD(54,18)
54 = 18 x 3 + 0 GCD(1260,198) = 18

(a) Write a recursive implementation of the Euclidean GCD function:
int gcd(int a, int b);
[Hint: Note that when the remainder is zero, the divisor will be the GCD]
(b) Write a short program to test your GCD function with the following values:

1280,198
197,13
120,60