Diophantine Equation Proof: solutions of $ax + by = dm$

Question

Given $\gcd(a,b) = d$, I want to prove that all integer solutions for the equation $ax + by = dm$ for some integer $m$ are of the form $x = mx_0 + \frac{b}{d}k$ and $y = my_0 - \frac{a}{d}k$. Here's what I have so far, but I am not sure how to finish it. Thanks in advance!

$ax + by = dm = (ax_0 + by_0)m = ax_0m + by_0m = a(x_0m) + b(y_0m)$

$ax + by = a(x_0m) + b(y_0m) \implies ax - a(x_0m) = b(y_0m) - by \implies a(x - x_0m) = b(y_0m -y)$

Since $gcd(a,b) = d$, $d$ divides $a$ and $b$. Thus, $\frac{a}{d}(x - x_0m) = \frac{b}{d}(y_0m - y)$

Answer 1

Well adding multiples of $b/d$ and $-a/d$ to any solutions $x$ and $y$ respectively will always result in another solution, because $a(x+kb/d)+b(y-ka/d)=dm$. So it seems you had forgotten a minus sign.

Note that $a/d$ and $b/d$ are coprime. Thus we can get the converse, that this exhausts all solutions, by noting that given two solutions $(x_1,y_1)$ and $(x_2,y_2)$, we have $a/d(x_1-x_2)=b/d(y_2-y_1) \stackrel{\text{Euclid's lemma}}{\implies} x_1-x_2=kb/d $. Similarly $y_2=y_1+ka/d$.

Answer 2

I understand the general Diophantine Equation proof when $ax + by = d,$ where $d = gcd(a,b),$ but I am stuck on how the proof changes for a multiple of the gcd

It is easy to transform (scale) one solution to the other, after recalling their linear genesis.

Recall that the general solution of a linear equation $\,L(x,y) := ax+by = d\,$ is the sum of any particular solution $\,(x_0,y_0)$ plus the general solution of the associated $\rm\color{#c00}{homogeneous}$ equation $\,L(x,y) = \color{#c00}0,\,$ which here is $\,(x,y) = k(b,-a)/d = (kb/d,-ka/d)$.

Now $L(x,y) = md\,$ has the same associated homogeneous equation so same homogeneous solution, and scaling yields a particular solution: $\, md = mL(x_0,y_0) = L(m(x_0,y_0)),\,$ so $m(x_0,y_0)$ is a particular solution. Therefore $\,L(x,y) = md\,$ has the general solution

$$(x,y)\, =\, \underbrace{m(x_0,y_0)}_{\rm particular} + \underbrace{k(b,-a)/d}_{\rm homogeneous}\, =\, (mx_0+kb/d,\, my_0-ka/d)\qquad $$

Summarizing $ $ the solution transformation process in general:

If $\,L\,\bar x_0 = d\ $ & $\ [L\,\bar x = 0 \!\iff\! \bar x = \bar x_h]\,$ then $\,L\,\bar x = d\,$ has general solution $\ \bar x\, =\, \bar x_0\, +\,\bar x_h$

so $\, L\,m\bar x_0 = md,\,$ therefore we deduce that: $\, L\bar x = md\,$ has general solution $\,\bar x = m\bar x_0 + \bar x_h$

e.g. from calculus: a simple linear differential equation

$\ D f\, =\, x\iff f = \frac{1}2 x^2 + c\,\ $ ($f= c\,$ is general solution of homogenous form $\,D f = 0)$

$D f = m x\!\iff\! f = \frac{m}2 x^2 + c,\,$ by simply scaling the particular solution by $\,m,\,$ as above, i.e. $\,\ D_x^{-1}(mx)\, =\, m\:\! D_x^{-1}(x),\ $ i.e. $\ \int_x mx = m\int_x x$.