Let $a,b,c$ be positive integers. Verify that Diophantine equation $ax + by = c$ has integer solution $x_0, y_0$ if and only if $GCD(a,b)|c$.


Diophantine $ax + by = c$ has integer solution $x_0, y_0$ implies $GCD(a,b)|c$. Factoring out $ GCD(a,b)$ from each side gives $$\frac{1}{GCD(a,b)}(ax + by) = \frac{1}{GCD(a,b)}c$$ which must still have an integer solution as $GCD(a,b)$ obviously divides both $a$ and $b$. If $GCD(a,b)$ does not divide $c$ there is no integer solution.

That $GCD(a,b)|c$ implies that $ax + by = c$ has integer solution $x_0, y_0$. Let $c = GCD(a,b)d$, where $d$ is integer.

$ax + by = GCD(a,b)d$; divide both sides by $GCD(a,b)$: Obtain $mx + ny = d$ with $GCD(m,n) = 1$. If $d$ is an integer and $GCD(m,n) = 1$ then $x,y$ must be integers as $mx + ny$ cannot be further divided evenly.


$ax + by = c$ has no solution implies $GCD(a,b)$ does not divide c.
$c = GCD(a,b)(\frac{ax}{GCD(a,b)} + \frac{by}{GCD(a,b)}) + r$

with $GCD(a,b) > 0, 0<r<GCD(a,b)$, r integer

$\frac{c}{GCD(a,b)} = \frac{ax + by}{GCD(a,b)} + \frac{r}{GCD(a,b)}$

  • $\begingroup$ It seems like you are attempting to prove the direction $(\Rightarrow)$. You should say more to make the reasoning clear. For the other direction you can use Bezout's identity for the gcd $\endgroup$ – Bill Dubuque Jul 28 '14 at 19:21
  • $\begingroup$ I don't think I need to use Bezout's as that is not mentioned in the chapter. Maybe the underlying principles. $\endgroup$ – miniparser Jul 29 '14 at 4:43
  • $\begingroup$ Bezout's identity for the gcd is the special case $\,c = \gcd(a,b),\,$ of the direction $(\Leftarrow),\,$ so you will need Bezout (or some equivalent). $\endgroup$ – Bill Dubuque Jul 29 '14 at 4:51
  • $\begingroup$ I reformatted the question. Please see math notation guide. $\endgroup$ – user147263 Jul 30 '14 at 21:36

If $(a,b)\mid c$, $\exists t\in \mathbb{Z}$ such that $t(a,b)=c$. As we know that there exists $x,y \in \mathbb{Z}$ such that $ax+by=(a,b)$, then choose the integers $x_0=tx$ and $y_0=ty$.

To prove the converse, if $x_0$ and $y_0$ be integers, then $(a,b)\mid x_0a$ and $(a,b)\mid y_0y$ implies $(a,b)\mid (x_0a+y_0b)$.

  • $\begingroup$ Wow, this is much more concise that what I stated. $\endgroup$ – KernelPanik Aug 11 '14 at 12:20

Let a,b,c be positive integers. Verify that Diophantine equation ax+by=c has integer solution x0,y0 if and only if GCD(a,b)|c.

=>: (how do you write the arrows?):

This was pretty much correct in my first attempt. More clearly:

If $ax + by = c$ has integer solution $x_0,y_0$(they exist - how do i draw that?) then $ax_0 + by_0 = c$. Divide both sides by $gcd(a,b)$. (See first attempt.) Then $gcd(a,b)|a, gcd(a,b)|b$ => $gcd(a,b)|(ax_0 + by_0)$ => $gcd(a,b)|c$.


This was pretty much wrong in my first attempt.

Let $gcd(a,b)|c$

Then exist e such that $c = gcd(a,b)*e$ and exist $x_1,y_1$ with $gcd(a,b) = ax_1 + by_1$

Multiply both sides by $e$: $gcd(a,b)*e = ax_1e + by_1e$

$a(x_1e) + b(y_1e) = c$, $(x_1e,y_1e)$ solution.

Attempt to prove both ways at once:

$ax + by = c$ has integer solution $ax_0 + by_0 = c$

Let $d = gcd(a,b)$; then $a = md,b = nd$:

$c = (md)x_0 + (nd)y_0 = d(mx_0 + ny_0)$

So $d$ divides $c$.

If either $ax_0 + by_0 <>($does not equal$) c$ or $gcd(a,b) $ does not divide $ c$

$c = (md)x_0 + (nd)y_0 = d(mx_0 + ny_0)$ would not be valid. kind of a stretch there.


Let $d=GCD(a,b)$ where $ {a,b,c,d,k_1,k_2,x,y} \in \mathbb Z$

(a) Positive: $d|c$

$$ d|a \implies d|ax \\ d|b \implies d|by $$

Since by the Division Theorem

$$ d|a \implies a/d=k_1\\ x(a/d)=k_1x \implies d|ax \\ d|b \implies b/d=k_2\\ y(b/d)=k_2y \implies d|by $$

Since $d|ax$ and $d|by$, and there exists a solution to $ax + by = c$, then $d$ divides both sides of the equation $ax + by = c$ and therefore $d|c$.

(b) Contrapositive: $d\not|c$

Given $d|a$ $$ d\not|ax \implies x\notin \mathbb Z $$ Likewise, given $d|b$ : $$ d\not|by \implies y\notin \mathbb Z $$


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.