1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Isn't d a multiple of c though, no the other way around so it would be $cl = d$ ? $\endgroup$ – Ben Knoll Oct 14 '15 at 15:16
  • $\begingroup$ 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. $\endgroup$ – Bill Cook Oct 14 '15 at 17:47
0
$\begingroup$

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.

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

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.