Consider the following algorithm. Note that the remainder function returns the remainder after integer division. EuclidsGcd IN: m and n are nonnegative integers, and m >= n 1. r = remainder(m, n) 2. while r > 0 3. mun 4. ner 5. r = remainder(m, n) 6. return n OUT: the greatest common divisor of the inputs is returned 1. Prove that the algorithm is partially correct. To do so, show that as when m and n are reassigned in each iteration of the loop their greatest common divisor does not change. 2. Show that the loop iterates O(log( mn)) times. (HINT: prove that m. n decreases by at least 1/3 of its prior value in each iteration of the loop). 3. Make an argument for full correctness that does not involve explicitly adding a proof of termination