The purpose of this problem is to set an upper bound on the number of iterations of the Euclidean algorithm.
A. suppose that m = qn + r with q > 0 and 0 ≤ r < n. Show that m/2 > r.
B. Let Ai be the value of A in the Euclidean algorithm after the ith iteration. Show that Ai+2 < Ai/2
C. Show that if m, n, and n are integers with (1 ≤ m, n ≤ 2n), then the Euclidean algorithm takes at most 2N steps to find gcd (m, n).