In this exercise, all integers are considered to be nonnegative, for simplicity. A divisor of an integer k is any integer d ≠ 0 such that k/d has no remainder. A common divisor for a set of integers is an integer that is a divisor for each integer in the set. Euclid’s algorithm for finding the greatest common divisor (GCD) of two nonnegative integers, m and n, can be written as follows:

1: procedure gcd(int m, int n)
2: if n = 0 then
3: answer ← m
4: else if m < n then
5: answer ← gcd(n, m)
6: else
7: r ← m - n ⋅ ⌊m/n⌋ //r is the remainder of mn
8: answer ← gcd(n, r)
9: end if
10: return ← anwser
11: end procedure

The preconditions for gcd(m, n) are that m ≥ 0, n ≥ 0 and m + n > 0.

Prove the following using induction:

a. If the preconditions of gcd(m, n) are satisfied, then the value that the function returns is some common divisor of m and n.
b. If the preconditions of gcd(m, n) are satisfied, then the value that the function returns is the greatest common divisor of m and n.