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$

1 Answer 1

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$
7
  • $\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, 2019 at 18:21
  • $\begingroup$ I don't know; I don't use Sage. $\endgroup$ Apr 13, 2019 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, 2019 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$ Apr 13, 2019 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, 2019 at 18:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .