Results 1 to 4 of 4

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

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    22

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,278
    Thanks
    670

    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....
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2011
    Posts
    22

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    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 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. if p divides x then is xy(mod p) = 0 ?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 11th 2011, 11:52 AM
  2. Replies: 2
    Last Post: May 1st 2011, 02:11 PM
  3. In Z[i], show that 1+i divides...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 21st 2010, 02:37 PM
  4. Replies: 1
    Last Post: February 23rd 2010, 12:36 PM
  5. Replies: 7
    Last Post: November 7th 2009, 04:05 AM

Search Tags


/mathhelpforum @mathhelpforum