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

• Hint: show that $ka+lb=1$ for some integers $a,b$ and use this to show that $gcd(k,l)=1$. – Mosquite Sep 14 '16 at 23:19

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

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.

• (+1) I think if $g$ is a factor of both $c$ and $m$ and $km+lc=g$, then $g=\gcd(c,m)$ – user84413 Sep 15 '16 at 0:35
• @user84413 You are right. I think that follows separately. – астон вілла олоф мэллбэрг Sep 15 '16 at 0:37

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