0
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ I don't even understand what $m, n$ are doing here. What are the hypotheses and data, what is searched? $\endgroup$ – Bernard Dec 25 '17 at 20:37
  • $\begingroup$ @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. $\endgroup$ – jiten Dec 25 '17 at 20:40
  • $\begingroup$ @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. $\endgroup$ – jiten Dec 25 '17 at 21:23
  • $\begingroup$ Yes, it's quite clear, and A.P.'s answer is quite fine. $\endgroup$ – Bernard Dec 26 '17 at 11:09
1
$\begingroup$
  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$.
$\endgroup$

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.