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 x ← a 2 y ← b 3 while x 6= y do 4 if x > y then 5 x ← x − y 6 else 7 y ← y − x 8 return x (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 integers. (d) using the termination property of your loop invariant, prove that procedure euclidean computes and returns the greatest common divisor of a and b.