How to prove that the condition is sufficient?

Question

I was solving a question at a programming website. The question specifies that a person is standing at point $(a, b)$ in an infinite 2D grid. He wants to know if he can reach point $(x, y)$ or not. The only operation allowed is to move to point $(a, a+b)$ or $(a+b, b)$ or $(a-b, b)$ or $(a, a-b)$. He can perform any number of these operations.

Now, I know that $\gcd(a + m*b, b)$ is same as $\gcd(a,b)$(I have proved it). Therefore, at the end $\gcd(x,y)$ should be equal to $\gcd(a,b)$. But how do I prove it to be sufficient?

Answer 1

Let $d = gcd(a, b) = gcd(x, y)$

For simplicity, I am assuming that $a, b, x, y$ are nonnegative. Otherwise, you can easily modify them until they are.

You can use the euclidean algorithm to get from $(a, b)$ to $(x, y)$:

The algorithm looks like this (quoting Wikipedia):

function gcd(a, b)
    while a ≠ b 
        if a > b
           a := a − b; 
        else
           b := b − a; 
    return a;

You can easily visualize this as an algorithm that repeatedly replaces $(a, b)$ either with $(a - b, b)$ or with $(a, b - a)$, until it reaches the point $(d, d)$.

Similarly, you can use this algorithm to get from $(x, y)$ to $(d, d)$. Now, we can take this sequence of steps, and reverse it. When doing so, an operation that takes $(a, b)$ to $(a - b, b)$ turns into an operation that takes $(o, p)$ to $(o + p, p)$ and an operation that takes $(a, b)$ to $(a, b - a)$ turns into an operation that takes $(o, p)$ to $(o, o + p)$.

So after reversing this path from $(x, y)$ to $(d, d)$, we get a path from $(d, d)$ to $(x, y)$. Concatenating this to the first path, we get a path from $(a, b)$ to $(x, y)$!

Edit: To clarify what you do if $a, b, x, y$ are negative: If $a < 0$, you can go from $(a, b)$ to $(a + b, b)$ to $(a + b, b - (a + b)) = (a + b, -a)$ to $(b, -a)$. If $b < 0$ as well, you can repeat this process to get to $(-a, -b)$. If $x$ or $y$ are negative, you can use the same method to go from $(x, y)$ to some point with nonnegative coordinates, and then reverse that path.