1
$\begingroup$

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?

  • 0
    You're right. I was not thinking properly. *facepalm*.2012-08-18

2 Answers 2

1

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.

  • 0
    Thanks! I also liked the remark about additive orders.2012-08-18
0

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$.

  • 0
    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.2012-08-18