Show that if $\gcd(a, b)\mid c$, then the equation $ax + by = c$ has infinitely many integer solutions for $x$ and $y$.

Question

Show that if $\gcd(a, b)\mid c$, then the equation $ax + by = c$ has infinitely many integer solutions for $x$ and $y$.

I understand that if there is one, solution for $ax+by =c$, then there are infinitely many solutions, just because you can solve it in different ways. However, I am not sure how to show this in a proof format.

Answer 1

The extended Euclidean algorithm guarantees a solution of $ax'+by'=d$ where $d=\mathrm{gcd}(a,b)$. Since $c$ is a multiple of $d$, say $c=d\ell$, we get: $ax'\ell+by'\ell=d\ell$ so $ax+by=c$ where $x=x'\ell$ and $y=y'\ell$. Thus there is at least one solution.

Next, notice that $a(x+bk)+b(y-ak) = ax+abk+by-abk=ax+by=c$.

Therefore, $x+bk$ paired with $y-ak$ also give a solution for any integer $k$. Thus there are infinitely many solutions.

Answer 2

If $$ax+by=c$$ then $$a(x-nb)+b(y+na)=c$$ with $n\in\mathbb{Z}$.

Answer 3

Euclidean algorithm says there is at least one solution.

if $ax + by = c$ then $a(x - b/gcd(a,b)) + b(y + a/gcd(a,b)) = ax + by = c$. Inductively there are infinitely many further solutions.