Determine if algorithm is infinite for the pair of positive integers $(n,m)$

Question

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

Answer 1

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)$.