Results 1 to 5 of 5

Math Help - Division problem with GCD

  1. #1
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2

    Division problem with GCD

    Let r, s, and t be integers, and suppose gcd(r,s)=1, r|t, and s|t.

    Prove rs|t.

    My work so far:

    I have attempted to use the definition of gcd and division to solve the problem.

    There exist integers a,b,c,d such that ra + sb = 1, rc = t, and sd = t.

    I can prove that t = r(rca)+s(brc), and t^2 = rs(cd), but I just can't get to the right answer.

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by tttcomrader View Post
    Let r, s, and t be integers, and suppose gcd(r,s)=1, r|t, and s|t.

    Prove rs|t.

    My work so far:

    I have attempted to use the definition of gcd and division to solve the problem.

    There exist integers a,b,c,d such that ra + sb = 1, rc = t, and sd = t.

    I can prove that t = r(rca)+s(brc), and t^2 = rs(cd), but I just can't get to the right answer.

    Thank you.
    As r|t, and s|t, each of the prime factors of s and t appear in the prime decomposition of t with at least the multiplicity that they appear in the decompositions of s and t.

    But as gcd(r,s)=1 they share no prime factors, so all the prime factors of rs appear in the prime decomposition of t with at least the multiplicity that they appear in the prime decomposition of rs. Hence rs|t.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by tttcomrader View Post
    Let r, s, and t be integers, and suppose gcd(r,s)=1, r|t, and s|t.

    Prove rs|t.

    My work so far:

    I have attempted to use the definition of gcd and division to solve the problem.

    There exist integers a,b,c,d such that ra + sb = 1, rc = t, and sd = t.

    I can prove that t = r(rca)+s(brc), and t^2 = rs(cd), but I just can't get to the right answer.
    Let, r,s,t be positive integers.
    And we know that \gcd(r,s)=1
    Thus, ar+bs=1 for some integers a,b.
    We also know that r|t \mbox{ and }s|t.
    Thus, t=rk and t=sj for some integers s,j.
    In the equation, ar+bs=1 multiply through by t to get,
    art+bst=t
    Now you problem was that you subsituted the wrong way.
    Meaning you subsituted first equation into first t value and second equation into second t value. You should have swaped them,
    ar(sj)+bs(rk)=t
    rs(aj+bk)=t
    Thus, we see that rs | t.

    Note, my method is better than CaptainBlank's because my was proven for all positive integers. He only proven it for intergers above 2 (otherwise they have no prime power decomposition).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThePerfectHacker View Post
    Note, my method is better than CaptainBlank's because my was proven for all positive integers. He only proven it for intergers above 2 (otherwise they have no prime power decomposition).
    Examine it more carefully, I think you will find it does cover the possibility that one or both or r and s are 1.

    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2
    I guess both methods are just as good.

    But I'm more familiar with the second one, but thank you both!!!

    KK

    P.S. PerfectHacker, have you by any chance figured out my post in Calculus? I been working on it, but I just can't get part a and part c to make sense. I finished the second problem btw, if you want me to show the works please let me know, well, I'm not sure if I got it right.

    Thank you again!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. division problem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: August 24th 2010, 05:02 PM
  2. Division Problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 29th 2010, 06:32 PM
  3. Division problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 5th 2009, 07:29 PM
  4. Division problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 28th 2009, 07:07 AM
  5. Division Problem
    Posted in the Algebra Forum
    Replies: 7
    Last Post: April 3rd 2008, 08:19 AM

Search Tags


/mathhelpforum @mathhelpforum