Object moves from $(1,1)$ to $(x,y)$ An object is at point $(1,1)$ and can move under the following rules.
(i) from $(a,b)$ to $(2a,b)$ or $(a,2b)$ 
(ii) from $(a,b)$ to $(a-b,b)$ when $a>b$ or $(a,b-a)$ when $b>a$
Find all order pairs $(x,y)$ such that the object can move to the point $(x,y)$.
Attempted work :
Since $\gcd(2a,b)$ and $\gcd(a,2b)$ are equal either $2\gcd(a,b)$ or $\gcd(a,b)$ and
$\gcd (a-b,b) = \gcd (a,b-a) = \gcd(a,b)$ so $\gcd (x,y)$ is a power of two.
Let $x=2^kx'$ , $y = 2^ky', \forall k \in \mathbb{N}_0$, where $\gcd(x',y')=1$
The object can move from $(x',y')$ to $(x,y)$ as follow.
$(x',y') \rightarrow (x',2y') \rightarrow (2x',2y')\rightarrow \ldots  \rightarrow (2^kx',2^ky')=(x,y)$
We need to show that it can move from $(1,1)$ to$(x',y')$
If $b$ is odd, by (i),  $(a,b) \rightarrow (2^{\phi(b)}a,b)$
Since $2^{\phi(b)}  \equiv 1 (\bmod {b})$, so by (ii), $(2^{\phi(b)}a,b) \rightarrow (a+b,b)$
If b is even, I still cannot show that $(a,b) \rightarrow (a+b,b)$
If I can get through this point, Reverse Euclidean Algorithm will finish the proof.
Can someone please help ?
 A: Here's an alternative proof . . .

Let $S$ be the set of points $(x,y) \in \mathbb{R}^2$ which can be reached from $(1,1)$ by a finite sequence of legal moves.

It's clear that in any one move, the coordinates stay integral and positive.

Let $\mathbb{N}$ denote the set of positive integers.

Let $T=\{(x,y) \in \mathbb{N}^2 \mid \gcd(x,y) = 2^k,\;\text{for some integer}\;k \ge 0\}$.

Claim $S=T$.

In any one move, the $\gcd$ of the coordinates either doubles, or stays the same. It follows that if $(x,y) \in S$, then $\gcd(x,y) = 2^k,\;\text{for some integer}\;k \ge 0\}$. 

Hence $S \subseteq T$.

Let $T_1=\{(x,y) \in \mathbb{N}^2 \mid \gcd(x,y) = 1\}$.

If $(x,y) \in S$, we can force both coordinates to double by the $2$-move sequence
$$(x,y) \to (2x,y) \to (2x,2y)$$
hence, to show $T \subseteq S$, it suffices to show $T_1 \subseteq S$.

Let $(x,y) \in T_1$. Our goal is to show $(x,y) \in S$.

Proceed by strong induction on $x+y$.

Since $(1,1) \in S$, the base case, $x+y = 2$, is verified.

Next suppose $x+y > 2$.

Since $\gcd(x,y) = 1$, we can't have $x,y$ both even.

Consider $2$ cases . . .

Case $(1)$:$\;$Exactly one of $x,y$ is even.

Without loss of generality, assume $x$ is even.
\begin{align*}
\text{Then}\;\;&\gcd(x,y)=1\\[4pt]
\implies\;&\gcd({\small{\frac{x}{2}}},y)=1\\[4pt]
\implies\;&({\small{\frac{x}{2}}},y) \in T_1\\[4pt]
\implies\;&({\small{\frac{x}{2}}},y) \in S&&\text{[by the inductive hypothesis]}\\[4pt]
\implies\;&(2({\small{\frac{x}{2}}}),y) \in S\\[4pt]
\implies\;&(x,y) \in S\\[4pt]
\end{align*}
Case $(2)$:$\;x,y$ are both odd.

Since $x+y > 2$, we can't have $x=y$, else $\gcd(x,y) > 1$.

Without loss of generality, assume $x < y$.

Note that $x < y \implies {\large{\frac{x+y}{2}}} < y$.
\begin{align*}
\text{Then}\;\;&\gcd(x,y)=1\\[4pt]
\implies\;&\gcd(x,x+y)=1\\[4pt]
\implies\;&\gcd(x,{\small{\frac{x+y}{2}}})=1\\[4pt]
\implies\;&(x,{\small{\frac{x+y}{2}}}) \in T_1\\[4pt]
\implies\;&(x,{\small{\frac{x+y}{2}}}) \in S&&\text{[by the inductive hypothesis]}\\[4pt]
\implies\;&(x,2({\small{\frac{x+y}{2}}})) \in S\\[4pt]
\implies\;&(x,x+y) \in S\\[4pt]
\implies\;&(x,y) \in S\\[4pt]
\end{align*}
Thus, in both cases, $(x,y) \in S$, which completes the induction, and hence completes the proof.
