Importancia de la DGC

Question

Entiendo el GCD matemáticamente, pero no sé dónde aplicarlo. Por ejemplo, hoy he visto este problema:

Adam está de pie en el punto $(a,b)\in\mathbb Z^2$ en una cuadrícula 2D infinita.
Quiere saber si puede alcanzar el punto $(x,y)$ o no.
Las únicas operaciones que puede hacer es moverse a los puntos $(a+b,b), (a,a+b), (a-b,b)\text{ or }(a,a-b)$ desde algún punto $(a,b)$ .
Se da la circunstancia de que puede desplazarse a cualquier punto de esta cuadrícula 2D, es decir, los puntos pueden tener un valor positivo o negativo $x$ (o $y$ ) coordenadas.

Dile a Adam si puede alcanzar $(x,y)$ o no.

La solución a este problema es sencilla:
Si $\gcd(x,y) = \gcd (a,b)$ entonces adam puede alcanzar $(x,y)$ de $(a,b)$ Si no es así, no.

Aunque esta solución sí funciona, no soy capaz de averiguar cómo se puede llegar a ella. ¿Cuál es el significado de $\gcd$ en esta pregunta?

Answer 1

La observación crucial es que $\gcd(u,v)=\gcd(v,u)=\gcd(u,u\pm v)$ .

De esto se desprende El algoritmo de Euclides para calcular el gcd.

La importancia del gcd en su problema es que la observación crucial implica que todos los puntos visitados por los movimientos permitidos tienen el mismo gcd. Por lo tanto, puedes dividir sus coordenadas por ese gcd y reducir el problema a una cuadrícula con espacio unitario y cuyos movimientos permitidos son a los vecinos inmediatos.

La observación crucial demuestra que si $(x,y)$ es accesible desde $(a,b)$ entonces $\gcd(x,y)=gcd(a,b)$ .

Para la inversa, nótese que el conjunto de todos los puntos que son alcanzables desde $(a,b)$ tienen coordenadas de la forma $am+bn$ con $m,n\in\mathbb Z$ . El conjunto de todas estas combinaciones lineales es el conjunto de todos los múltiplos de $\gcd(a,b)$ .