0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Does sage has any inbuilt function which enables us to plug in the values of a,b,c and returns result? $\endgroup$ – Stefan Apr 13 at 18:21
  • $\begingroup$ I don't know; I don't use Sage. $\endgroup$ – Misha Lavrov Apr 13 at 18:21
  • $\begingroup$ 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 $\endgroup$ – Stefan Apr 13 at 18:31
  • $\begingroup$ 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$.) $\endgroup$ – Misha Lavrov Apr 13 at 18:33
  • $\begingroup$ 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? $\endgroup$ – Stefan Apr 13 at 18:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.