Number theory: Can we reach from $(x_0,y_0)$ to $(x_1,y_1)$ ,with following transitions? Given $2$ points in 2-dimensional space $(x_s,y_s)$ and $(x_d,y_d)$, our task is to find whether $(x_d,y_d)$ can be reached from $(x_s,y_s)$ by making a sequence of zero or more operations.
From a given point $(x, y)$, the operations possible are:
a) Move to point (y, x)
b) Move to point (x, -y)
c) Move to point (x+y, y)
d) Move to point (2*x, y)

Now i am pretty sure this has something to do with gcd's but m not able to formalize my approach, Can someone intuitively explain how can we figure out if a particular state is reachable from the current state?
 A: Gcd is invariant under operations a,b,c. Gcd may double under operation d. So the transition is possible if either $\gcd(x_s,y_s)=\gcd(x_d,y_d)$ or $2^n\gcd(x_s,y_s)=\gcd(x_d,y_d)$ for some $n\in\mathbb N$ where we assume $\gcd(x,y)=\gcd(|x|,|y|)$.
Note that $$\gcd(x,y)|ax+by\;\forall\;a,b\in\mathbb Z$$ We can justify our claim that under c gcd is invariant using Bezout's lemma.
If $\gcd(x,y)=d\;$$$\exists a,b\in\mathbb Z: ax+by=d\implies a(x+y)+(b-a)y=d\implies\gcd(x+y,y)|d$$
Again $d|x+y,y\implies d|\gcd(x+y,y)$. As both are positive $d=\gcd(x+y,y)$. 
For operation d, note that $x/d,y/d$ can't have any common factor other than $1$, it would violate the fact that $d=\gcd(x,y)$. So if $y/d$ is odd $\gcd(2x,y)=d\gcd(2x/d,y/d)=d$. If $y/d$ is even $\gcd(2x,y)=d\gcd(2x/d,y/d)=2d$. 
A: First note that the actions $a, b, c$ can be inverted:
$$ a^{-1}=a,\quad b^{-1}=b,\quad c^{-1}=b\circ c\circ b.$$
Therefore "reachable by zero or more applications of $a, b, c$" is an equivalence relation, which we shall denote by $\sim$.
By applying $b$ if necessary, we see that each $(x,y)\in\Bbb Z$ is equivalent to some $(x',y')$ with $y'\ge 0$.
Let $m\in\Bbb N_0$ be minimal such that $(x,y)\sim(x',m)$ for some $x'\in\Bbb Z$.
As $bab(x',m)=(-x',m)$, there exist $x'$ with $(x',m)\sim (x,y)$ and $x'\ge 0$. 
Let $n\in\Bbb N_0$ be minimal with $(n,m)\sim(x,y)$.
As $(n,m)\sim (m,n)$ we conclude $n\ge m$.
If $m>0$ we arrive at $(n,m)\sim (n,-m)\sim (n-m,-m)\sim (n-m,m)$, contradiction.
Hence $m=0$.
As $\gcd(y,x)=\gcd(x,-y)=\gcd(x+y,y)$, we conclude that $(x,y)\sim(\gcd(x,y),0)$ and $(x,y)\sim(u,v)\iff \gcd(x,y)=\gcd(u,v)$. (Another way to put this: the steps $a,b,c$ allow us to implement Euklid's algorithm).
If we now add operation $d$, the situation changes, we do not have an equivalence relation any more.
Let us write $(x,y)\to(u,v)$ if $(u,v)$ can be obtained from $(x,y)$ by zero or more applications of $a,b,c,d$.
By repeated application of $d$ we find $(x,0)\to (2^kx0)$ for any $k\in\Bbb N_0$, hence $(x,y)\to (u,v)$ whenever $$\gcd(u,v)=2^k\gcd(x,y)$$ with $k\in\Bbb N_0$. On the other hand $\gcd(2x,y)\in\{\gcd(x,y),2\gcd(x,y)\}$ and hence this sufficient condition is also necessary.
