Help needed in diophantine equation!

Revision en1, by find_X, 2020-08-06 15:26:19

I was practicing some questions on diophantine equation when I saw a classical jump problem where we had to determine if we can reach to point 'n' from point 0 by taking jumps of length 'a' or 'b' in either direction(i.e. left or right) on an infinite number line. However I was thinking for variation of this question where we have an additional constraint that at any point of time in our path, we should never go outside the range [0, m] where 'm'is any number greater than or equal to 'n'. Out of all the testcases that I was able to make, I observed that such constraint holds if n is divisible by gcd(a, b) (same as the normal variaton), but I am not able to prove it mathematically for this variation. Can anyone help me in this?

Formally: Can anyone give me a mathematical proof that if n is divisible by gcd(a, b) then there exists a way in which we can reach 'n' in such a way that we are always within the range [0, m] (m >= n), or if my assertion is wrong then I want to know about the flaw in this statement.

Tags #number theory, #gcd, diophantine equation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English find_X 2020-08-06 15:26:19 1061 Initial revision (published)