Given the linear diophantine equation
$$ax+by=c $$
I have to show that it has solution if and only if $gcd(a,b)$ divides $c$.
$$1)\Rightarrow $$
Let $m=gcd(a,b)$ then
$$a'x+b'y=c'$$
where $gcd(a',b')=1$, but how can I continue from here?
$$2) \Leftarrow $$
I don't know even how to start. I've never studied seriously number theory until now, and I'm self-studying so this is difficult to me. Any help will be appreciated.
Should I use the division theorem? I mean that, for $a,b\neq0 \in \mathbb{Z}$ there exists numbers $q, 0\leq r <|b|$ such that $a=bq+r$
$$ $$
$\Rightarrow)$Every number that divides $a$ and $b$ divides $c$, so $gcd(a,b)|c$.
$\Leftarrow)$If $gcd(a,b)|c$, then $\frac{a}{gcd(a,b)}x+\frac{b}{gcd(a,b)}y=\frac{c}{gcd(a,b)}$ has a solution. Here $\frac{a}{gcd(a,b)}$ and $\frac{b}{gcd(a,b)}$ are coprime. In other words, you need to show: if $a,b$ coprime, then there exists $x,y$ such that $ax+by=1$. To show this, you need to use Euclidean algorithm.
Showing $a,b$ coprime $\Rightarrow ax+by=1$.
With loss of generality, assume $a>b>0$. By division we have $$a=bq+r_1$$where $0<r_1<b$. Notice that $gcd(b,r_1)|a$, and hence $gcd(b,r_1)=1$ as $a,b$ coprime. Similarly, we have $$b=r_1q_1+r_2$$with $gcd(r_1,r_2)|b$ and so $gcd(r_1,r_2)=1$ since $b,r_1$ coprime. Continue this division and say it eventually stops at $$r_{n-1}=r_nq_n$$Then $r_n=1$ since $gcd(r_{n-1},r_n)=1$.
For simplicity, let us assume $r_2=1$. Then $r_1q_1=b-1$. Subing in the first equation gives $$aq_1=bq+(b-1)$$which is what you want.