if $gcd(a,b)=gcd(a,b,c)$ then I need to prove that $ax+by=c$ has solution in $\mathbb Z$

Question

if $gcd(a,b)=gcd(a,b,c)$ then I need to prove that $ax+by=c$ has solution in $\mathbb Z$ that is: $gcd(a,b)|c$

but how can I prove it with the given hypothesis?

Answer 1

let $g = gcd(a,b) = gcd(a,b,c)$, $c=d*g$

it exists $u,v$ such as $a*u+b*v=g$, $a*u*d+b*v*d=g*d=c$

Answer 2

Hints:
I.
$\gcd(n,m)=n\iff n\mid m.$
II.
$\gcd(a,b,c)=\gcd(\gcd(a,b),c).$

Hope this helps.

Answer 3

You're pretty much there. $d = (a,b) = (a,b,c)$. So in particular, $d \mid c$.

It seems you already know that we can write $ax'+by'=d$ For $x', y' \in \mathbb Z$, and then multiplying by a suitable integer will give you the solution you're looking for.

Answer 4

First divide $a,b,c$ by $\gcd(a,b)$ so that we can assume that $a,b$ (and therefore $a,b,c$) are relatively prime.

Apply now Euclid's algorithm to $a,b$. This will give you equations:

$a=bq_1+r_1$, $b=q_2r_1+r_2$, ..., $r_n=q_{n+1}r_{n-1}+r_{n+1}$, where $r_{n+1}=1$ is the $\gcd(a,b)$.

Substituting backwards these equations we get $ax+by=1$. Multiply the whole equation by $c$ to get $a(cx)+b(cy)=c$.

Answer 5

Hint $ $ Recall $ \ d = \gcd(a,b,c)\,\Rightarrow\, \color{#c00}d\mid a,b,\color{#c00}c,\ $ i.e. the $\rm\,g\color{#0a0}{cd}$ is a $\rm\color{#0a0}{c}ommon\ \color{#0a0}{d}ivisor$ of its arguments.

In your case $ \ d = \gcd(a,b)\,$ thus $\, \color{#c00}{d}\mid \color{#c00}c\, $ becomes $\,\gcd(a,b)\mid c,\,$ as desired