Is there a way to find positive values for unknown of Diophantine Equations?

Question

I have a equation as follow ax+by =c where the value of x and y are unknown. This is a 2 unknown linear diophantine problem. I tried to dig into sage if they have any methods for that, but couldn't find any.

Is there a programmatically a way to solve x and y in such cases. I am considering a , b and c as very large numbers. and more importantly looking for positive solutions

Answer 1

We can use the extended Euclidean algorithm, implemented in Sage as xgcd, to find $x', y'$ such that $$ax'+ by' = \gcd(a,b).$$ For $ax+by=c$ to have a solution, $c$ must be divisible by $\gcd(a,b)$ (since the left-hand side is certainly divisible by $\gcd(a,b)$). Therefore we can solve the above equation first, and then multiply to get a solution to $ax+by=c$: $$ a \left(x' \cdot \frac{c}{\gcd(a,b)}\right) + b \left(y' \cdot \frac{c}{\gcd(a,b)}\right) = c. $$ This is not necessarily positive, but starting from one solution $(x_0,y_0)$ to $ax+by=c$, all other solutions are parametrized as $(x_0 + kb, y_0 - ka)$. So for example if $x_0 < 0$ and $y_0 > 0$, you can take $k = \lfloor \frac{y_0}{a}\rfloor$ (the maximum $k$ that keeps $y$ positive) and see if this makes $x$ positive. Or if $x_0 > 0$ and $y_0 < 0$ you can similarly try $k = -\lfloor \frac{x_0}{b}\rfloor$.

In either case, you will either get a nonnegative solution (do you want strictly positive? then take $\lfloor \frac{y_0-1}{a}\rfloor$ or $-\lfloor \frac{x_0-1}{b}\rfloor$ instead), or you will know that there are no nonnegative solutions.