Greatest common divisor relatively prime integers proof

Question

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.

Answer 1

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.

Answer 2

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$.

Answer 3

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} $$