If $k$ and $l$ are positive integers such that $k\mid l$, show that for every positive integer $m$, $1+(k+m)l$ and $1+ml$ are relatively prime.

Question

If $k$ and $l$ are positive integers such that $k\mid l$, show that for every positive integer $m$, $1+(k+m)l$ and $1+ml$ are relatively prime.

My approach: I wrote

$(k+m)(1+ml)-m(1+(k+m)l)=k=la$ where $a>0$

Now, I took both sides modulo $l$. The right side is $0 \pmod l$ whereas the left side is $k \pmod l$ Thus, $l\mid k$.

But $k\mid l$ by the question so, $k=l$ ... But then how to proceed?

Answer 1

We can employ of the fact that $\gcd(x, y)=\gcd(x+ny,y),\forall n\in\mathbb Z.$
So $\gcd(1+(k+m)l,1+ml)=\gcd(kl,1+ml).$ But $\gcd(kl,1+ml)\mid m(kl)-k(1+ml)=-k\mid l.$ Hence $\gcd(kl,1+ml)\mid 1+ml-ml=1.$
Hope this helps, and please inform me if you don't understand something, thanks.

Answer 2

Suppose that $p$ is a prime with $p\mid 1+ml$ and $p\mid 1+kl+ml$. Then $p\mid kl$ and $p\mid l$ because of $k\mid l$. This contradicts $p\mid 1+ml$. Hence $gcd(1+ml,1+ml+kl)=1$.