Addition problem

Let me remind you of a problem I've mentioned last week: you are given three non-negative numbers up to 10^18: A, B and S. At each step, you can replace either A or B with A+B. Is it possible to make at least one of A or B equal to S?

The first step is to find the greatest common divisor of A and B: gcd(A, B) = G. If S is not divisible by G, then clearly we can't get it. Otherwise, let's divide everything by G - in other words, we've reduced the problem to the case where gcd(A, B) = 1.

Now, it's clear that each number we can obtain is equal to N*A+M*B for some non-negative N and M. But is any pair of non-negative N and M possible? No. For example, it's not hard to see that we can't obtain 2*A+2*B. We start with A and B, continue to A+B and B (A+B and A is similar), and then it's not hard to see that the multiplier of B in all following numbers will be greater than the multiplier of A.

It helps to look at this problem as a geometric one. Let's plot N on one axis and M on the other axis. We start with vectors (0, 1) and (1, 0). At each step we add one of our vectors to another. We can notice an invariant: the area of the triangle induced by our vectors stays equal to 0.5! The area is one half of the vector's cross product, and the cross product doesn't change when we add one vector to another. This picture is similar to what happens when studying continued fractions.

In other terms, if our numbers are N₁*A+M₁*B and N₂*A+M₂*B, then N₁*M₂-M₁*N₂ is always equal to 1. One consequence of this invariant is that N₁ and M₁ (or N₂ and M₂, for that matter) are relatively prime: gcd(N₁, M₁)=1. So we have limited the set of obtainable numbers to those where gcd(N, M)=1.

But it's not hard to see the reverse also holds! Suppose gcd(N,M)=1. That means there exist such numbers X and Y that N*X+M*Y=1. Let's say that X is non-negative and Y is non-positive. Then we can define N₁=N, M₁=M, N₂=-Y, M₂=X, and we obtain the above invariant: N₁*M₂-M₁*N₂=1. But then we can repeatedly subtract either (N₁, M₁) from (N₂, M₂) or vice versa, reconstructing the path from (1,0), (0,1) from the end.

So the original problem boils down to: is there a way to pick non-negative N and M such that gcd(N, M)=1 and N*A+M*B=S? We can solve the latter Diophantine equation in the standard way using the Extended Euclidean algorithm, obtaining N(T)=N₀+B*T, M(T)=M₀-A*T. The condition on N and M being non-negative gives us a range of possible values of T, and in case that range is empty, we have no solution. But in case it's non-empty, how to check if N and M will be relatively prime for some T in that range?

And here's the key trick: I've guessed that we can just check possible values of T until we find one that gives relatively prime N and M, and we will either find such T quickly or run out of possible values of T quickly. Why? I didn't prove it during the contest, and the more I try to prove it now, the more it looks it might be false :) Any ideas?