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

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

## 1 Answer

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.

• Does sage has any inbuilt function which enables us to plug in the values of a,b,c and returns result? – Stefan Apr 13 at 18:21
• I don't know; I don't use Sage. – Misha Lavrov Apr 13 at 18:21
• In my case the gcd(a,b) is 1. So I could find x' and y' in which x' is negative and y' is positive but how could I recover the x and y from it. If I plug those values in the (a*x'*c) + (b*y'*c) == c it gives FALSE and that equation doesn't seem to have any unknown involved – Stefan Apr 13 at 18:31
• If $ax'c + by'c$ is not equal to $c$, then $ax' + by'$ is not equal to $1$ and you are not finding $x'$ and $y'$ correctly. (Or the $\gcd$ is not actually $1$.) – Misha Lavrov Apr 13 at 18:33
• oh my bad, It works. I used the 0th element as x' . oops, So now the case is x' is negative and y' is positive. What shall I do next to get both of them positive? – Stefan Apr 13 at 18:36