3
$\begingroup$

Is there any way to find if there are any positive solutions of a linear Diophantine equation of the form

$$ax + by = c$$

It is not necessary to find such $x$ and $y$. I just want to determine if such solutions exist with $x \in \mathbb{W} $ and $y \in \mathbb{W}$.

$\endgroup$
2

2 Answers 2

8
$\begingroup$

Here is an outline of an answer based on Section 5.1, "The Equation $ax + by = c$," of I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley (New York), 1991. You can prove some of the statements with the help of this theorem.

We assume that $a$, $b$, and $c$ are integers; that $a$ and $b$ are not both zero; and that solutions refers to integer solutions only.

If $c$ is not a multiple of gcd($a,b$) = $g$, there are no solutions, and you have your answer. Otherwise, there are infinitely many solutions which form an arithmetic progression in both "directions," so continue with the following checks to determine whether any of those solutions are positive.

If $a$ or $b$ is zero, it is simple to determine whether there are any positive solutions.

If $a$ and $b$ have opposite signs, there are infinitely many positive solutions. To see that, view the equation as a line with a positive slope in the Euclidean plane. Some infinite part of the line must lie in the first quadrant.

The final case is that $a$ and $b$ have the same sign; it suffices to assume that $a$ and $b$ are positive. View the equation as a line with a negative slope. If $c$ is not positive, neither is the $y$-intercept, so no part of the line lies in the first quadrant; hence, there are no positive solutions.

If on the other hand $c$ is positive, it is possible to derive a formula for the number of positive solutions: Let $x_0,y_0$ be one solution, which we can find using the Euclidean algorithm. Then all solutions are of the form $$x = x_0 +\frac{kb}{g},\qquad y = y_0 - \frac{ka}g$$ where $k$ is an integer, so you want to find $k$ such that $$x_0 +\frac{kb}g > 0,\text{ and } y_0 -\frac{ka}g > 0,$$ which is equivalent to $$\frac{-gx_0}b < k <\frac{gy_0}a.$$ For an inequation such as $m < k < n$, the integer lower bound is $\lfloor m\rfloor + 1$ and the integer upper bound is $\lceil n\rceil - 1 = -\lfloor -n\rfloor - 1$. Therefore we have $$\left\lfloor\frac{-gx_0}b\right\rfloor +1 \le k \le -\left\lfloor -\frac{gy_0}a\right\rfloor -1.$$ Thus, the number of of positive solutions is $$\begin{align}&-\left\lfloor -\frac{gy_0}a\right\rfloor -1 -\left(\left\lfloor\frac{-gx_0}b\right\rfloor +1\right) + 1 \\ =& -\left\lfloor -\frac{gy_0}a\right\rfloor - \left\lfloor\frac{-gx_0}b\right\rfloor - 1.\end{align}$$

$\endgroup$
2
  • 1
    $\begingroup$ Take $c = 405$, $a = 55$, $b = 350$. Clearly $405 = a + b$ so $x = y = 1$. But $c < \frac{ab}{g}$. You are saying there's a positive solution if and only if $c > \frac{ab}{g}$. $\endgroup$
    – Laraconda
    Commented May 23, 2020 at 2:48
  • $\begingroup$ @Laraconda I thank you for catching a mistake. I corrected my answer. For your example, the solution you give is the only positive one. $\endgroup$
    – user0
    Commented May 27, 2020 at 17:45
1
$\begingroup$

user0's answer is awesome and I want to make some supplementary notes here:

  1. Since the solutions exists only if $g|c$, we can divide the equation by $g$, and assume WLOG $\gcd(a, b) = 1$

  2. If we accept non-negative integers instead of positve integers, the maximum c such that the equation is unsolveable would be
    $$c =ab-a-b$$.

To prove this, we first prove the Diophantine equation is unsolveable for such c. Assume $x, y \ge 0$ are solutions, then $$ ab-a-b = ax+by \\ ab-a-ax = b+by \\ a|b+by, b|b+by $$ $ab|b+by$ since $g=\gcd(a,b)=1$ ; But $ab > ab-a-ax$, contradiction.

Second we prove the Diophantine equation is solvable for any $c > ab-a-b$. As we accept $x, y$ to be $0$, we can change a little bit the inequalities from user0

$$ x_{0} + \frac{kb}{g} > -1 \\ y_{0} - \frac{ka}{g} > -1 \\ \frac{g(-1 - x_{0})}{b} < k < \frac{g(1 + y_{0})}{a} $$

This open interval has length $$ \frac{g(ax_0+by_0+a+b)}{ab} = \frac{g(a+b+c)}{ab} > g = 1 $$ and must contain an integer.

$\endgroup$
2
  • $\begingroup$ $ab-a-b < c$ appears only to be a sufficient but not a necessary condition for having non-negative integer solutions to $ax+by=c$. E.g. when $a=10$, $b=3$, $c = 13$, obviously $x=y=1$. But $ab-a-b = 17 > c$ $\endgroup$ Commented Sep 25, 2023 at 1:23
  • $\begingroup$ By using the same argument in the edited answer by @user0, I would suggest to check $-\left\lfloor -\frac{g\left( 1+y_0 \right)}a\right\rfloor - \left\lfloor-\frac{g\left( 1+x_0\right)}b\right\rfloor - 1 \ge 1$ for existence of non-negative integers, rather than $ab-a-b<c$. $\endgroup$ Commented Sep 25, 2023 at 7:45

You must log in to answer this question.

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