elementary number theory - dividing by integers

Let $m,q,r,s$ be integers.

Suppose GCD($r$,$s$) = 1.

Suppose $m|qr$ and $m|qs$.

Show that $m$ divides $q$.

This was a result that was assumed in class. I couldn't see the reasoning behind it though.. please provide some guidance/hints.

---

What I've tried so far:

I note that since $(r,s)=1$, then either $m$ does not divide $r$, or $m$ does not divide $s$.

I suppose that $m$ does not divide $r$.

Then I note that $m|qr$ but m does not divide $r$.

I try to come up with a contradiction by assuming that $m$ does not divide $q$, but since $m$ isn't prime, this doesn't get me far.

Am I going down the wrong path? Is there something I'm failing to consider?

Answer

Hint $\ $ By basic gcd laws $\rm\ m\:|\:qr,qs\:\Rightarrow\:m\:|\:(qr,qs)\, =\, q(r,s)\, =\, q\:$ by $\rm\:(r,s) = 1.\ \ $ QED

Or, instead of gcd laws one may use the Bezout identity: $\rm\:jr + ks = 1\:$ for some $\rm\:j,k\in\Bbb Z,\:$ hence

$$\rm\ m\:|\:qr,qs\:\Rightarrow\:m\:|\:j(qr)\!+\!k(qs) = q(jr\!+\!ks) = q\ \ \ {\bf QED}$$

Note how the proof by gcd laws eliminates the variables $\rm\,j,k,\:$ which only serve to obfuscate.

Remark $\ $ It can also be intepreted in terms of orders of elements. Namely, the hypothesis viewed modularly says $\rm\: mod\ m:\ r\cdot q\equiv 0\equiv s\cdot q,\:$ which implies that the additive order of $\rm\:q\:$ divides the coprime integers $\rm\:r,s\:$ so it must be $1,\,$ i.e. $\rm\:1\cdot q\equiv 0,\:$ i.e. $\rm\:m\:|\:q.\:$ This viewpoint is discussed further in some of my posts on order ideals.