Problem 1 The greatest common divisor (GCD) of two integers a and b is defined as the largest integer that can divide both a and b without a remainder. For example, the GCD of 30 and 54 is 6, whereas the GCD of 7 and 5 is 1. The following procedure was developed by Euclid to compute the greatest common divisor of two positive integers a and b. In this exercise, we will prove the correctness of this algorithm. procedure EUCLIDEAN(a, b) 1 ta 2 ytb 3 while x + y do 4 if x > y then + -y 6 else y Y-3 8 return OCT (a) State the loop invariant for the while loop in this procedure. (b) Prove the loop invariant. (c) Prove that procedure EUCLIDEAN always terminates provided that a and b are positive inte- gers. (d) Using the termination property of your loop invariant, prove that procedure EUCLIDEAN computes and returns the greatest common divisor of a and b