1. gcd recursion theorem Prove the god recursion theorem: For any a ∈ NU {0} and be N, we have gcd

(a,

b) = gcd

(b, a mod b).

(2.25)

(Hint: Show that both expressions are divisors of each other. Why does this guaran-

tee their equality?)