Lets say I have a diophantine equation ,

aX - bY = c

Now, for some (a,b,c) I may not have any integer solution at all. But lets say , I write the equation in this way ,

aX - bY = c + p

p is an integer . (positive or negative)

So, I can increase the value of c by (c+p) if there are no solution for (a,b,c). I need to find a triplet (a,b,c+p) for which solution exist and p is minimum(absolute value).

If , already I have solution for (a,b,c) then p is just 0.

How to solve this problem ?

  • $\begingroup$ My idea so far ,G = gcd(a,b) = k*(c+p) , so , p = (G/k-c) $\endgroup$ – anon Jun 4 '16 at 17:52
  • $\begingroup$ $$aX-bY=c$$ has an integer solution as soon as $\gcd(a,b)$ is a divisor of $c$, so you just have to look at the intersection of two arithmetic progressions. $\endgroup$ – Jack D'Aurizio Jun 4 '16 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.