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!
Note that moving from one point to another in the described way will not change gcd of the x and y co-ordinates (Euclidian's theorem) so it is not possible to a point with different gcd of x and y co-ordinates. It is always possible to reach co-ordinates with same gcd of x and y co-ordinates as one possible way is to reach (gcd,0) or (0,gcd) first, then to the the required point.
You can always reach (gcd,0) or (0,gcd) by the way we calculate gcd.
Take a look at this theorem: Given integers a and b, not both of which are zero, there exist integer x and y such that GCD(a,b)=ax+by. i.e. GCD of two numbers can be expressed as linear combination of the two numbers.