Diophantine equation $ax + by = c$ has an integer solution $x_0, y_0$ if and only if $\gcd(a,b)|c$

Solution 1:

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)$.

Solution 2:

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.