Use the Euclidean algorithm to compute the GCDs of the following pairs of integers. State how many interations each one takes to compute, and the value of the potential s

2. (a) Use the Euclidean algorithm to compute the GCDs of the following pairs of integers State how many iterations each one takes to compute, and the value of the potential s at each stage. Verify that indeed si+ You are encouraged to use a computer for this part. i. (77,143) ii. (90, 504) ii. (376, 475) iv. (987, 1597) (b) Try to find pairs of inputs (x, y such that the number of iterations of Euclid(, y) is "large", that is, as close as possible to the upper bound of loga/2) that we derived in lecture. Can you come up with a hypothesis about what kinds of inputs yield the worst-case running time? (Hint: Question 2(a)i is a worst-case erample.)