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.

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

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

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 $\displaystyle a$ divides $\displaystyle bc$ and $\displaystyle (a,b)=1$, then $\displaystyle a$ divides $\displaystyle c$.

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