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

divisibilityelementary-number-theoryprime numbers

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?

Best Answer

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.