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?

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

  • $\begingroup$ Thanks! I also liked the remark about additive orders. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – confused Aug 18 '12 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.