Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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