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.
No comments:
Post a Comment