The purpose of this problem is to set an upper bound on the number of iterations of the Euclidean algorithm.

a. Suppose that \(m=q n+r\) with \(q>0\) and \(0 \leq rr\).

b. Let \(A_{i}\) be the value of \(A\) in the Euclidean algorithm after the \(i\) th iteration. Show that

\[
A_{i+2}<\frac{A_{i}}{2}
\]
c. Show that if \(m, n\), and \(N\) are integers with \(\left(1 \leq m, n, \leq 2^{N}ight)\), then the Euclidean algorithm takes at most \(2 N\) steps to find \(\operatorname{gcd}(m, n)\).