Prove that if m is prime and m|kl then either m|k or m|l.

Question

Proofs homework question, here's what I've figured out thus far.

Suppose m doesn't divide k. We need to then prove that m|l. If m doesn't divide k and m is a prime then we know m and k are co-prime - hcf (m,k) = 1. Which means 1 = ks + mt (for some integers; s,t).

I'm not really sure where to go from here to prove that m|l based on these facts, help?

Answer 1

From your work, you can conclude that

$$l = (kl) s + m (lt)$$

Now $m | kl$ by assumption, so $m$ divides the right hand side of this equation. Hence it divides the left.

Answer 2

The Bezout-based proof is a bit more intuitive interpreted modulo $\,m.\,$ Notice that the Bezout identity $\,\color{#c00}{1 = \gcd(k,m)} = a k\! +\! b m\,$ becomes $ $ mod $\,m\!:\ 1\equiv ak,\,$ hence $\,\color{#c00}{k^{-1}} \equiv a$ exists mod $\,m.\,$ Hence $\, m\mid k\,\ell\,\Rightarrow\,k\,\ell\equiv 0\!\!\!\!\! \overset{\large\quad \times\,\color{#c00}{k^{-1}}}\Rightarrow\!\!\ell\equiv 0\,\Rightarrow\,m\mid \ell.\ $ Therefore, mod $\,m,\,$ the proof amounts to the simple fact that elements $\,k\,$ coprime to the modulus are, by Bezout, invertible, so cancellable.

Remark $\ $ If you know the gcd Distributive Law $\rm\color{#0a0}{(DL)}$ you can write the proof very concisely

$$m\mid k\ell,m\ell\ \Rightarrow\ m\mid (k\ell,m\ell)\overset{\rm\color{#0a0}{(DL)}} = \color{#c00}{(k,m)}\ell = \ell\qquad\qquad$$

Answer 3

$$\frac\ell m=\frac{\ell\cdot1}m=\frac{\ell(ks+mt)}m=s\cdot\frac{k\ell}m+\ell t.$$Since $\ell,s,t$ are integers, and since $\frac{k\ell}m$ is an integer, it follows that $\frac\ell m$ is an integer, Q.E.D.