If $gcd(m,n) = gcd(m,k) = gcd(n,l) =1$ show that $gcd(kn+lm, mn) = 1$

Question

I started by showing that $gcd(kn, m) = gcd(lm, n) = 1$, and with Bezout's lemma I wrote $knx + my = 1$ and $lmx' + ny' = 1$. Then I solved for my and $ny'$ and multiplied them together to get:

$$ mnyy' = (knx - 1)(lmx' - 1) = klmnxx' - knx - lmx' + 1. $$

Rearranging gives: $$ mn(yy' - klxx') + knx + lmx' = 1. $$

So it appears all that is left to do is to show that $x = x'$ I think, however I am lost on how to do this. Any help is welcome!

Answer 1

$\begin{align} &(kn+lm,\color{#c00}m) = (kn,m)=1\\ &(kn+lm,\color{#0a0}n)\, = (lm,n)\, = 1\end{align}$ $\,\Rightarrow\, (kn+lm,\color{#c00}m\color{#0a0}n) = 1\ $ by Euclid (see here & here)

Remark $ $ If you don't know that form of Euclid we can prove it directly

$(a,m)(a,n) = (aa,am,an,mn) = (a(a,m,n),mn) = (a,mn)\ $ by $\ (a,m,n) = 1$

You could also use Bezout above instead of gcd laws (distributive, commutative, associative), e.g. see the comparison here. But that yields a less general proof.

Note that this can be expressed in the language of fractions as follows

$\qquad m,n$ coprime, $\dfrac{k}m,\dfrac{l}n$ reduced $\,\Rightarrow\, \dfrac{k}m+\dfrac{l}n = \dfrac{kn+lm}{mn}\,$ reduced

Answer 2

With pure Bezout, it can be done, but it's quite a gymnastic...

$\begin{cases} mA+kB=1 & \times\ nE & \implies mnAE+knBE=nE=1-mF \\ && \implies m(nAE+F)+kn(BE)=1 \\ \\ nC+lD=1 & \times\ mF & \implies mnCF+lmDF=mF=1-nE \\ && \implies n(mCF+E)+lm(DF)=1 \\ nE+mF=1\end{cases}$

By adding $0$

$\begin{cases} 0=lm(BE)-m(lBE) & \text{we get} & (kn+lm)(BE)+m(nAE+F-lBE)=1 \\ 0=kn(DF)-n(kDF) & \text{we get} & (kn+lm)(DF)+n(mCF+E-kDF)=1 \end{cases}$

Now we multiply these lines together:

$\begin{cases}(kn+lm)W+mX=1\\(kn+lm)Y+nZ=1\end{cases}\implies (kn+lm)(WY+nZW+mXY)+mn(XZ)=1$