I'm reading up on diophantine equations and one of the theorems is that

"if $x,y$ is any solution of $ax + by = c$, then it is of the form $x_0 +\dfrac{b}{d}t ,\, y_0 - \dfrac{a}{d}t$ where $d = \gcd(a,b)$"

(Where $(x_0, y_0)$ is a particular solution.)

They subtract the two equations, then divide by d to give $\dfrac{a}{d}(x-x_0) + \dfrac{b}{d}(y-y_0) = 0$

Then they claim that $\dfrac{b}{d}$ must divide $x-x_0$ but I don't understand why, could someone please explain?


Let $a'=\frac{a}{d}$ and $b'=\frac{b}{d}$. Then $a'(x-x_0)+b'(y-y_0)=0$. This can be rewritten as $$b'(y_0-y)=a'(x-x_0).\tag{1}$$ Since $d=\gcd(a,b)$, the numbers $a'$ and $b'$ are relatively prime. From (1) we can see that $b'$ divides $a'(x-x_0)$. Since $\gcd(b',a')=1$, it follows that $b'$ divides $x-x_0$.

  • $\begingroup$ Oh Thanks! now I get the relatively prime bit, since they're both divided by the gcd. $\endgroup$ – Marek Kurczynski Jul 8 '15 at 14:36
  • $\begingroup$ @MarkK This can e viewed a bit more conceptually as unique fractionization, and the first part is a special case of the fact that fact that the general solution of an (affine) linear equation is the sum of any particular solution plus the general solution of the associated homogeneous equation $\endgroup$ – Bill Dubuque Jul 8 '15 at 14:57
  • $\begingroup$ @MarkK: You are welcome. $\endgroup$ – André Nicolas Jul 8 '15 at 14:58

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.