1
$\begingroup$

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.

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

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

$\endgroup$
1
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.