Let $a,b,c \in \mathbb{Z} \backslash \{ 0\}$. Prove there exists $x$, $y$ such that $ax+by=c$ if and only if $(a,b)|c$

Question

Title really says most of it. I tried reverse induction but it got too convoluted so I figured it probably wasn't the best way of proving it

Answer 1

Let $(a,b) = g$.

---

Suppose that $g \mid c$.

Then there exists $x',y' \in \mathbb Z$ such that $ax' + by' = g$. Since $g \mid c$, then $c = c'g$ for some $c' \in \mathbb Z$. So

$$c = c'g= c'(ax'+by') = a(c'x') + b(c'y') = ax + by.$$

Where $x = c'x'$ and $y = c'y'$. So the equation $ax+by = c$ has a solution.

Suppose that the equation $ax+by = c$ has a solution.

Since $g \mid a$ and $g \mid b$, there exists $a',b' \in \mathbb Z$ such that $a = ga'$ and $b=g'b$. So

$$c = ax + by = (ga')x + (gb')y = g(ax' + by').$$

Hence $g \mid c$.