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 C-0 2 ykb 3 4 5 6 while x # y do if x >y then 21 Y else y + y - x return x 7 8 (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