2. Euclid's algorithm Use the god recursion theorem to prove that Euclid's algo-

rithm, written as a recursive program in pseudo-code below, computes gcd

(a, b):

Euclid(BigInteger

a, BigInteger

b) {

if (b== 0) return a;

else return Euclid (b,a mod b);

}