Why is it that moving from one point to another involve GCD ?

Revision en1, by SASANQUA, 2020-07-17 09:23:06

I was reading a solution for a problem which states that:

Given $$$(x_0, y_0)$$$ as the starting point, is it possible to move from it to another point $$$(x_1, y_1)$$$ ? In one move at a point $$$(x, y)$$$, you can move to four possible positions: $$$(x+y, y), (x-y, y), (x, y+x), (x, y-x)$$$. ($$$-10^9\leq x_0,x_1,y_0,y_1\leq10^9)$$$

The solution says that it is possible to move from $$$(x_0, y_0)$$$ to $$$(x_1, y_1)$$$ iff $$$GCD(x_0, y_0) = GCD(x_1, y_1)$$$. Other than that, there are no other explanations why it is like that. Can anyone explain? Thanks!

Tags gcd, 2d

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English SASANQUA 2020-07-17 09:23:06 598 Initial revision (published)