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

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.

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

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.

• Isn't d a multiple of c though, no the other way around so it would be $cl = d$ ? – Ben Knoll Oct 14 '15 at 15:16
• No. The gcd divides evenly into c which means c is a multiple of d. If c was a proper divisor of d there would be no solution. – Bill Cook Oct 14 '15 at 17:47

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.

• Arggh. Jean-Francois answer is better. – fleablood Oct 14 '15 at 3:59