Number theory: Can we reach from $(x_0,y_0)$ to $(x_1,y_1)$ ,with following transitions?

Question

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?

Answer 1

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

Answer 2

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.