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. Euclids 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 m //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.

Hints: If d is a divisor of k, how can you rewrite k in terms of d? How do you show that two sets are equal?

Personal Note to Expert: The question is asking for a proof using induction, meaning base case, induction step and an assumption step, then proving the statement preferrably using an example based on the psuedocode provided.

5 (BvG 3.6 (modified)) 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) answer-m 3: 4: 5: 6: 7: else if m