Teoría de números: ¿Podemos llegar de$(x_0,y_0)$ a$(x_1,y_1)$, con las siguientes transiciones?

Question

Dados$2$ puntos en el espacio bidimensional$(x_s,y_s)$ y$(x_d,y_d)$, nuestra tarea es determinar si se puede llegar a$(x_d,y_d)$ desde$(x_s,y_s)$ haciendo una secuencia de cero o más operaciones. Desde un punto dado$(x, y)$, las operaciones posibles son:

 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)
 

Ahora estoy bastante seguro de que esto tiene algo que ver con los gcd, pero no puedo formalizar mi enfoque. ¿Puede alguien, de manera intuitiva, explicar cómo podemos averiguar si un estado en particular es accesible desde el estado actual?

Answer 1

Mcd es invariante bajo las operaciones a,b,c. Mcd puede en virtud de la doble operación d. Por lo que la transición es posible si $\gcd(x_s,y_s)=\gcd(x_d,y_d)$ o $2^n\gcd(x_s,y_s)=\gcd(x_d,y_d)$ algunos $n\in\mathbb N$ donde asumimos $\gcd(x,y)=\gcd(|x|,|y|)$.

Tenga en cuenta que $$\gcd(x,y)|ax+by\;\forall\;a,b\in\mathbb Z$$ podemos justificar nuestra afirmación de que en virtud de la c mcd es invariante en el uso de Bezout del lexema. Si $\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$$ De nuevo $d|x+y,y\implies d|\gcd(x+y,y)$. Como ambos son positivos $d=\gcd(x+y,y)$.

Para la operación d, tenga en cuenta que $x/d,y/d$ no tienen ningún factor común distinta de $1$, lo que violaría el hecho de que $d=\gcd(x,y)$. Así que si $y/d$ es extraño $\gcd(2x,y)=d\gcd(2x/d,y/d)=d$. Si $y/d$ incluso $\gcd(2x,y)=d\gcd(2x/d,y/d)=2d$.

Answer 2

Primera nota de que las acciones de $a, b, c$ puede ser invertida: $$ a^{-1}=a,\quad b^{-1}=b,\quad c^{-1}=b\circ c\circ b.$$ Por lo tanto, "alcanzable por cero o más aplicaciones de $a, b, c$" es una relación de equivalencia, que lo vamos a denotar por $\sim$. Mediante la aplicación de $b$ si es necesario, podemos ver que cada una de las $(x,y)\in\Bbb Z$ es equivalente a un $(x',y')$$y'\ge 0$. Deje $m\in\Bbb N_0$ ser mínima tal que $(x,y)\sim(x',m)$ algunos $x'\in\Bbb Z$. Como $bab(x',m)=(-x',m)$,$x'$$(x',m)\sim (x,y)$$x'\ge 0$. Deje $n\in\Bbb N_0$ mínimo en $(n,m)\sim(x,y)$. Como $(n,m)\sim (m,n)$ llegamos a la conclusión de $n\ge m$. Si $m>0$ llegamos a $(n,m)\sim (n,-m)\sim (n-m,-m)\sim (n-m,m)$, contradicción. Por lo tanto $m=0$. Como $\gcd(y,x)=\gcd(x,-y)=\gcd(x+y,y)$, llegamos a la conclusión de que $(x,y)\sim(\gcd(x,y),0)$$(x,y)\sim(u,v)\iff \gcd(x,y)=\gcd(u,v)$. (Otra manera de poner esto: los pasos a $a,b,c$ nos permiten implementar Euklid del algoritmo).

Si ahora añadimos la operación $d$, la situación cambia, no tenemos una relación de equivalencia. Vamos a escribir $(x,y)\to(u,v)$ si $(u,v)$ puede ser obtenida a partir de a $(x,y)$ por cero o más aplicaciones de $a,b,c,d$. Mediante la aplicación repetida de $d$ nos encontramos con $(x,0)\to (2^kx0)$ cualquier $k\in\Bbb N_0$, por lo tanto $(x,y)\to (u,v)$ siempre $$\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)\}$ y por lo tanto, esta condición suficiente, es necesario también.