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?

• It is not just that $m$ does not divide $r$. It is that GCD $(m,r)=1$. This is a strictly stronger statement. – Ravi Aug 18 '12 at 2:35
• why is GCD(m,r)=1? Couldn't I have m=6, s = 20, r = 21? – confused Aug 18 '12 at 2:38
• You're right. I was not thinking properly. facepalm. – Ravi Aug 18 '12 at 6:36

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.

• Thanks! I also liked the remark about additive orders. – confused Aug 18 '12 at 3:09

You need to consider each prime dividing $m$. It can't divide both $r$ and $s$, so its highest power in $m$ must divide $q$.

• Got it! thanks that was very helpful. Oh, wait. nope, seems I made a mistake. I'll keep trying to look at what you've said and see if I get somewhere. – confused Aug 18 '12 at 2:44