# If r divides xy and s divides xy but gcd(r,s) =1: show that r divides xy/s

• Oct 8th 2011, 12:28 PM
restin84
If r divides xy and s divides xy but gcd(r,s) =1: show that r divides xy/s
The question is:

r divides xy and s divides xy but gcd(r,s) = 1. Show that r divides xy/s

I am having a hard time finding a starting point for this problem. I believe I could use
xr + ys = 1 since gcd(r,s) = 1. I also know that since r|xy then there is an integer n such that xy = rn and since s|xy then there is an integer m such that xy = sm. Are these facts enough to do this proof or is there something that I am unaware of? I'm not looking for the answer to the problem as much as I am looking to be nudged in the right direction.
• Oct 8th 2011, 01:09 PM
Deveno
Re: If r divides xy and s divides xy but gcd(r,s) =1: show that r divides xy/s
here's my take on it.

we know that xy = rn = sm.

so m = rn/s = xy/s. what we'd like to do is show n/s is an integer, and then we're done.

so factor s into powers of distinct primes.

for each prime factor p of s, we have p|rn, but p does not divide r (because gcd(r,s) = 1).

thus p | n.

now if p^k | s, we must likewise have p^k | n (why?), so....
• Oct 8th 2011, 03:30 PM
restin84
Re: If r divides xy and s divides xy but gcd(r,s) =1: show that r divides xy/s
if p^k | s then p^k | n by transitivity of divisibility
since all p^k of s divide n can I say that n mod s = 0 therefore n/s must be an integer(call it i)
now xy/s = ri which shows that xy/s is clearly a multiple of r and r | xy/s
• Oct 8th 2011, 04:16 PM
melese
Re: If r divides xy and s divides xy but gcd(r,s) =1: show that r divides xy/s
Quote:

Originally Posted by restin84
The question is:

r divides xy and s divides xy but gcd(r,s) = 1. Show that r divides xy/s

I am having a hard time finding a starting point for this problem. I believe I could use
xr + ys = 1 since gcd(r,s) = 1. I also know that since r|xy then there is an integer n such that xy = rn and since s|xy then there is an integer m such that xy = sm. Are these facts enough to do this proof or is there something that I am unaware of? I'm not looking for the answer to the problem as much as I am looking to be nudged in the right direction.

Applying the following theorem gives a short solution:
If $a$ divides $bc$ and $(a,b)=1$, then $a$ divides $c$.

So $r$ divides $xy=s\cdot(xy/s)$. But $(r,s)=1$ and therefore $r$ must divide $xy/s$.