1. Prove that the algorithm is partially correct. To do so, show that as when and are reassigned in each iteration of the loop their greatest common divisor does not change. 2. Show that the loop iterates times. (HINT: prove that decreases by at least 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.