Let $a,b,c \in \mathbb{Z}, a,b \ne 0, d = (a,b)$. Then the equation $ax+by = c$ has an integer solution $x,y$ iff $d \mid c$. In that case there are infinitely many solutions.

Need to derive general solution using the parametric form.

The first issue concerns with "a" step in the proof, which is ubiquitously applied to derive the parametric form. This step is common in books, and MSE alike even though the answers at MSE are innovative sort of, as here.

I am repeating verbatim the contents of LeVeque's book titled: Fundamentals of Number Theory, pg. 39 and pg. 40, to show the context of the two issues.

By exploiting the connection we have established between the GCD of two integers and linear combinations of them, it is easy to analyze the linear Diophantine equation in two unknowns $x$ and $y$,

(6) $ax + by = c, \text{ s.t. } a,b,c,x,y \in \mathbb{Z}$

First suppose that $(a,b) = 1$. Then we know that for suitable $x,y \in \mathbb {Z}, ax + by = 1$, so $cx, cy$ give a solution of (6). If $x, y$ and $x_0, y_0$ are any two distinct solutions of (6), then

$a(x - x_0) + b(y - y_0) = c-c =0 \text{ <--------------Issue 1 }$.

Since $(a,b) =1$, the equation $\frac{a}{b} = -\frac{y-y_0}{x - x_0}$ shows that for some $t \in \mathbb {Z}$

(7) $y - y_0 = -at, \text{ } x - x_0 = bt$.

Contrariwise, if $x_0, y_0$ satisfy (6) and $t$ is an integer (including $0$), then the $x,y$ determined by (7) also satisfy (6). Hence, (7) provides a general solution of (6), in this case. As a passing remark to readers who have studied linear systems of algebraic or differential equations, we remark that a general solution of (6) has thus been given as the sum of a particular solution of the in-homogeneous equation and a general solution of the homogeneous equation, $ax + by = 0$.

Now suppose that in (6), $(a,b) = d$. If $d \nmid c$, there are obviously no solutions. If $d \mid c$, has exactly the same set of solutions as the simplified equation $\frac{a}{d}x + \frac{b}{d}y = \frac{c}{d}$, and since $(\frac{a}{d}, \frac{b}{d}) = 1$, we already know these. Hence we have the following theorem.

Theorem 2.9 A necessary and sufficient condition that the equation (6) have a solution $x,y$ is that $d \mid c$, where $d = (a,b)$. If there is one solution - say $x_0, y_0$ - there are infinitely many; they are exactly the numbers

(8) $x = x_0 + \frac{b}{d}t, y = y_0 -\frac{a}{d}t, t \in \mathbb {Z} \text{ <--------------Issue 2 }$

Issue 1 : Why the value of $c$ is assumed to be the same. For me, (6) can have unique solutions based on the values of $c$ that are a multiple of $d$. Hence $c$ is a particular value of the linear combination, that should not be repeated from one unique solution to another for given $a,b$.

Issue 2: I hope that the reason for (8) having change of sign in $x$ and $y$ terms is because of the needed cancellation of the terms containing $t$.

The same idea can be expressed as : There are infinitely many solutions given by the pairs :

(i) $x = x_0 \pm \dfrac{bt}{d}, y = y_0 \mp \dfrac{at}{d}$,

where $x_0, y_0$ is any particular solution, and $t$ is parameter.

I expect some reference(s) or enough detail for the latter issue.


For issue 1: When we assume that $x_1, y_1$ is a solution a solution to $a x + b y = c$, we know that $a x_1+ b y_1 = c$.

For issue 2: modify the original equation by dividing both sides by $d$, then apply the reasoning that led to the equations in (7), finally isolating $x$ and $y$

  • $\begingroup$ You mean that in issue 1, there are non-unique values of $x,y$ for the same set of values of $a,b,c$ in EEA. $\endgroup$ – jiten Dec 12 '17 at 7:34
  • $\begingroup$ Yes. And the arguments that you posted show how to find them. An easy example would be when a=1, b=1, c=0. Then all pairs with y= -x will be solutions. $\endgroup$ – abstractnonsense Dec 12 '17 at 7:56
  • 1
    $\begingroup$ What you're seeking sounds like it's in the text that you posted. One suggestion would be to work through the above proof with concrete values for a, b and c. Perhaps a=2, b=3, c=2. I suspect that might help clear things up for you. $\endgroup$ – abstractnonsense Dec 12 '17 at 8:03
  • 1
    $\begingroup$ x=-2,y=2; x=-2+3,y=2-2;...;x=-2+3t,y=2-2t, etc. $\endgroup$ – abstractnonsense Dec 12 '17 at 8:45
  • 1
    $\begingroup$ In general by "reversing" Euclid's algorithm. See for example math.stackexchange.com/a/2559609/296521 $\endgroup$ – abstractnonsense Dec 12 '17 at 9:20

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.