a. Show that if Stein's algorithm does not stop before the \(n\)th step, then

\[C_{n+1} \times \operatorname{gcd}\left(A_{n+1}, B_{n+1}ight)=C_{n} \times \operatorname{gcd}\left(A_{n}, B_{n}ight)\]

b. Show that if the algorithm does not stop before step \((n-1)\), then

\[A_{n+2} B_{n+2} \leq \frac{A_{n} B_{n}}{2}\]

c. Show that if \(1 \leq A, B \leq 2^{N}\), then Stein's algorithm takes at most \(4 N\) steps to find \(\operatorname{gcd}(m, n)\). Thus, Stein's algorithm works in roughly the same number of steps as the Euclidean algorithm.
d. Demonstrate that Stein's algorithm does indeed return \(\operatorname{gcd}(A, B)\).