3
$\begingroup$

This question already has an answer here:

If you have a Linear Diophantine Equation, $ax + by = c$, such that $a, b, c$ are constants is there an efficient way to check that there exists some pair $X, Y \in \mathbb N$?

I recognize that I could find every integer solution and then check for every pair if $(X, Y)$ are natural numbers, but this is very indirect and inefficient; I was wondering if there is a more direct and efficient manner to determine the existence of such a solution.

$\endgroup$

marked as duplicate by Dietrich Burde, Daniel W. Farlow, Shailesh, E. Joseph, user223391 Oct 31 '16 at 0:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Sorry, this was not the correct one, there is also one for positive solutions, e.g., Bill's answer here. $\endgroup$ – Dietrich Burde Oct 30 '16 at 17:25
  • $\begingroup$ The other question is very relevant, but I think this one is asking whether there exists a natural number solution, not asking to find any explicit solutions or whether there exist integer solutions. $\endgroup$ – 6005 Oct 30 '16 at 17:26
  • $\begingroup$ Yes, just proving the existence of a natural number solution $\endgroup$ – BlurryZombie Oct 30 '16 at 17:37
  • $\begingroup$ if the gcd of a and b does not divide c then there is no solution. $\endgroup$ – Brandon Thomas Van Over Oct 30 '16 at 17:52
  • $\begingroup$ True, yet there are cases where it proves there is an integer solution but this doesn't necessarily entail that there is a natural solution. $\endgroup$ – BlurryZombie Oct 30 '16 at 17:57
1
$\begingroup$

Perhaps the following might be useful.

Let $a, b > 0$ be coprime integers. Then for all $$ c \ge (a-1)(b-1) $$ there are $x, y \ge 0$ such that $$ a x + b y = c. $$ (The inequality is best possible, in the sense that $c = (a-1)(b-1) -1$ cannot be expressed in this form.)

I have a proof (which is very simple and straightforward indeed) written up in some notes in Italian, but can translate it if needed.


Euclid's algorithm yields positive integers $u, v$ such that \begin{equation*} a u - b v = 1, \end{equation*} where we may have had to swap the roles of $a$ and $b$. The solutions of \begin{equation*} a x + b y = c \end{equation*} are of the form \begin{equation*} a (c u - b t) + b (a t - c v) = c, \end{equation*} for some integer $t$. We ask ourselves, when is there a $t$ such that \begin{equation*} c u - b t > -1, \qquad a t - c v > -1, \end{equation*} that is
\begin{equation*}\tag{ineq} \frac{c u}{b} + \frac{1}{b} > t > \frac{c v}{a} - \frac{1}{a}. \end{equation*} A sufficient condition for such a $t$ to exist is that the difference between the two bounds in (ineq) is strictly larger than $1$, so that there is an integer in between. In fact one has \begin{equation*} \frac{c u}{b} + \frac{1}{b} - (\frac{c v}{a} - \frac{1}{a}) = c \cdot \frac{a u - b v}{a b} + \frac{1}{b} + \frac{1}{a} = \frac{c}{ab} + \frac{1}{b} + \frac{1}{a} \ge 1 + \frac{1}{ab} > 1, \end{equation*} as $a u - b v = 1$, and $c \ge (a - 1) (b - 1) = ab - a - b + 1$, so that $$ \frac{c}{ab} \ge 1 - \frac{1}{b} - \frac{1}{a} + \frac{1}{ab}. $$

$\endgroup$
  • $\begingroup$ Could you please write this proof? I am very interested in it. $\endgroup$ – user4201961 Feb 7 '17 at 13:30
  • 1
    $\begingroup$ @user4201961, I have written it up. $\endgroup$ – Andreas Caranti Feb 7 '17 at 18:13

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