Greatest common divisor relatively prime integers proof Let $gcd(c,m)=g.$
Show that if $kc+lm=g$, then $gcd(k,l)=1$
I can see that its true with this example 
Let $c=5, m=15$. We have $gcd(5,15)=5$, then let $k=-2$ and $l=1$ $gcd(-2,1)=1$ but I'm not sure how to generalize it.
 A: A more concise version of Aston's answer: By assumption, $g\mid c$ and $g\mid m$, and by definition, $\gcd(k,l)\mid k$ and $\gcd(k,l)\mid l$. Therefore $g\cdot \gcd(k,l)\mid kc$ and $g\cdot \gcd(k,l)\mid lm$, hence $g\cdot \gcd(k,l)\mid (kc+lm)=g$, forcing $\gcd(k,l)=1$.
A: Since $km + lc = g$, and $g = \gcd(c,m)$, it follows that $g$ divides $c$ and  $g$ divides $m$. Hence, $\frac{c}{g}$ and $\frac{m}{g}$ are well defined and are integers.
Then:
$$
km+lc = g \implies k\bigg(\frac{c}{g}\bigg) + l\bigg(\frac{m}{g}\bigg) = 1
$$
Hence, the number $1$ is part of the set of linear combinations of $k$ and $l$. Hence, it must be the lowest positive number in that collection, which is by definition the $\gcd$ of $k$ and $l$. Hence, $\gcd(k,l) = 1$.
In this problem, $g$ need not have been the $\gcd$ of $c$ and $m$, it was enough that it should be a factor of both.
A: We have
$$
\left\{ \begin{gathered}
  \gcd (c,m) = g \hfill \\
  kc + lm = g \hfill \\ 
\end{gathered}  \right.\quad  \Rightarrow \quad \left\{ \begin{gathered}
  \gcd (c',m') = 1 \hfill \\
  kc' + lm' = 1 \hfill \\ 
\end{gathered}  \right.
$$
Suppose $ \gcd (c,m) \ne 1$ , then you would get the contradiction
$$
\begin{gathered}
  \gcd \left( {k,l} \right) = q \ne 1\quad  \Rightarrow \quad k'c' + l'm' = \frac{1}
{q}\quad  \Rightarrow \quad  \hfill \\
   \Rightarrow \quad \text{at}\,\text{least}\,\text{one}\,\text{of}\,k',l',c',m'\text{not}\,\text{integer} \hfill \\ 
\end{gathered} 
$$
