# Non-negative solutions of linear Diophantine Equations with all positive coefficients.

A new approach (not found anywhere else) is given in book by Uspensky, Heaslet, titled Elementary Number Theory, as detailed below for finding non-negative solutions of a linear Diophantine Equation(LDE) $ax + by =c, \exists a,b,c \gt 0 \in \mathbb {Z}$, so that the slope of the line is negative (signs of $a,b$ are the same).

I am stuck and want (at least) help in the below highlighted portion (of which, my doubts are listed in the end) to enable me start understanding the text:

Dividing $x,y$, respectively, by $b,a$, have: $x = bm + r, y = an +s$, the substitution of these expressions yields: $ab(m+n) + ar + bs = c.\text{ }{ -(i)}$
By division can represent $c$ as: $c = abq + R, 0 \le R \lt ab,\text{ }{ -(ii)}$
whence, together with (i), it follows: $ar + bs - R = ab(q - m - n).$

This shows that $ab \mid (ar + bs - R), \text { but } ar + bs \lt 2ab;$ consequently $ar + bs - R \lt 2ab,$
and on the other hand: $ar +bs - R \gt -ab,$ and so the integer $\frac{ar+bs-R}{ab}$ lies in range $(-1,2) \implies 0,1$ as possible values;

i.e. \begin{align} ar + bs = R , \text{ }{ and, } & \ ar + bs = R + ab \text{ }{ -(iii)}\\ \end{align} and correspondingly\begin{align} m + n = q , \text{ }{ and, } & \ m + n = q - 1 \text{ }{ }\\ \end{align} If $(a,b)=1$, then in eqn. (iii) exactly one has solution in non-negative integers $r \lt b \text{, }{ and }$ $s\lt a.$ To prove this, let $r_0, s_0$ denote some particular solution of the first equation in (iii), i.e., $ar + bs = R$. Then all solutions of this equation will be given by: \begin{align} r = r_0 - bt , \text{ }{ } & \ s = s_0 + at \text{ }{ }\\ \end{align} & among them there is only one in which $0 \le r \lt b.$ The corresponding value of $s \lt a$, as $bs \le R \lt ab.$ Moreover $s \gt -a,$ since $bs \ge -ar \gt -ab.$

Now if it happens that $s \ge 0$, then the equation $ar + bs = R$ has a solution of the required kind and the solution is unique. But, then it is impossible to satisfy the other equation in the same manner. For $r+b, s$ will satisfy this equation, & all other solutions of it will be given by \begin{align} r + b -bt , \text{ }{ } & \ s + at \text{ }{ }\\ \end{align}and the only way to make $0 \le r+b - bt \lt b$ is to take $t = 1$, but then $s + at \ge a$. If, on the contrary, $s \lt 0$, then numbers $0 \le r \lt b, 0 \le s+a \lt a,$ will satisfy the second equation.

Thus there are only two cases to consider:
(1) $ar + bs = R$ is solvable in non-negative integers;
(2) not solvable in this manner.

In (1), $m+n = q$ has exactly $q+1$ solutions in non-negative integers:\begin{align} m = 0, 1, 2, ..., q\\ n = q, q-1, q-2, ..., 0\\ \end{align} and correspondingly there are $q+1$ solutions of the equation $ax +by = c$ in non-negative integers.

For (2), $m +n = q-1$ has exactly $q$ solutions in non-negative integers \begin{align} m = 0, 1, 2, ..., q-1\\ n = q-1, q-2, q-3, ..., 0\\ \end{align} to which correspond again $q$ solutions of the proposed equation in non-negative integers.

The summary of the results of the above discussion follows:
$ax + by = c, \exists a,b,c \gt 0, (a,b) =1$ has $q+1$ or $q$ solutions, as the equation $ar +bs = R$ has solutions in non-negative integers $r \lt b, s \lt a$, or not.
Note: $c = ab.(q) + R$.

My doubts in the highlighted portion:
(i) Why not $(q-m-n) \mid (ar +bs - R)$?
(ii) Why $ar +bs \lt 2ab$?

• I don't even understand what $m, n$ are doing here. What are the hypotheses and data, what is searched? – Bernard Dec 25 '17 at 20:37
• @Bernard This is stated in the very first line : $x =mb + r, y = na +s$. Hypothesis is all positive coefficients of linear Indeterminate equation (and that forms the data too by giving values of $a,b,c$), while the search is for non-negative solutions. – jiten Dec 25 '17 at 20:40
• @Bernard I hope my OP is clear now, and if there is any thing doubtful, I will either copy the text's image or do the needful. – jiten Dec 25 '17 at 21:23
• Yes, it's quite clear, and A.P.'s answer is quite fine. – Bernard Dec 26 '17 at 11:09

1. Sure, assuming that $q-m-n \neq 0$ you can also say that $(q-m-n) \mid (ar+bs-R)$, but is that useful? Here we are using the fact that $ab \mid (ar+bs-R)$ to derive the conclusion that $$q-m-n = \frac{ar+bs-R}{ab} \in \{0,1\}.$$
2. By Euclidean division we have $x=bm+r$ and $y=an+s$ with $\mathbf{0 \leq r < b}$ and $\mathbf{0 \leq s < a}$. Hence $0 \leq ar < ab$ and $0 \leq bs < ab$.