SASANQUA's blog

By SASANQUA, history, 4 years ago, In English

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
  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can always reach (gcd,0) or (0,gcd) by the way we calculate gcd.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.