Determine if algorithm is infinite for the pair of positive integers $(n,m)$ Given any pair of positive integers (n,m) and the following algorithm:
The smaller integer(n) doubles and the bigger one(m) becomes `m-n` until m is equal to n

Example: 
    (7,1) -> (6,2) -> (4,4) - Algorithm is finite
    (21,9) -> (12,18) -> (24,6) -> (18, 12) - Algorithm is infinite

 A: 1. Proof that the algorithm ends if $m+n = 2^k \gcd(m,n)$ by induction on $k$.
First notice that for any $m,n \in \Bbb N, {m\over2} + n + {m\over2} = n+m$ thus $n+m$ is a loop invariant. What's more $m+n = 2\gcd(m,n) \implies m=n$. This is our base case.
Now assume $m\lt n$ and $m+n = 2^k\gcd(m,n)$ for a certain integer $k\ge2$.
Then $$\begin{align}
\gcd(2m, n-m) &= \gcd(2m, n+m)\\ 
&= \gcd(2m, 2^k\gcd(n,m))\\ 
&= 2\gcd(m, 2^{k-1}\gcd(m,n))\\ 
&=2^i \gcd(m,n)
\end{align}$$
for a certain $i\ge1$.
Therefore $m+n = 2^{k-i}\gcd({m\over2}, n+{m\over2})$ and since $k-i \lt k$, the algorithm finishes (note that $k-i \gt 0$).
2. Proof that the algorithm ends only if $m+n = 2^k \gcd(m,n)$ by structural induction.
Note that the solutions can be constructed by induction by :


*

*$n,n$ is solution for any integer n

*$m,n$ where $n\gt m$ is solution iff $2m, n-m$ is solution.


If $m=n$ then $m+n = 2\gcd(m,n)$, this is our base case.
Lets assume that the algorithm ends for a certain pair $\{m,n\}$ where $n+m = \gcd(m,n)2^k$ for a certain integer k, then the preceding pair was necessarily $\{{m\over2},n+{m\over2}\}$ or $\{{n\over2},m+{n\over2}\}$. Let's assume the latter without loss of generality (since $n$ and $m$ play a symmetrical role).
Then $2^i\gcd({n\over2}, m+{n\over2}) = \gcd(m,n)$ for a certain integer $i$ (see above) and therefore ${n\over2} + m + {n\over2} = 2^{k+i}\gcd({n\over2}, m+{n\over2})$.
Therefore any pair $\{m,n\}$ for which the algorithm finishes satisfies $\exists k \in \Bbb N^*, m+n = 2^k \gcd(m,n)$
Conclusion the algorithm finishes for $n,m$ iff $\exists k \in \Bbb N^*, m+n = 2^k \gcd(m,n)$.
