Results 1 to 7 of 7
Like Tree2Thanks
  • 1 Post By florian
  • 1 Post By johan121

Math Help - Greatest Common Divisor

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    United Kingdom
    Posts
    4
    Thanks
    1

    Greatest Common Divisor

    Hi all!
    I'm an OAP(male) from the UK
    I dabble in maths irregularly.
    I have a degree from the OU (thats the Open University)
    I do maths for fun!
    I have the following problem. Can you help?

    if gcd(m,n)=1, prove that gcd(mn,m+n)=1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2012
    From
    Jacksonville, FL
    Posts
    30
    Thanks
    4

    Re: Greatest Common Divisor

    Suppose gcd(m,n) = 1.

    Let d be a common divisor of mn and (m+n). Then there exist x, y s.t.

    xd = mn and yd = m+n.

    xd = m(yd - m) or (my - x)d = m^2. And similarly,
    xd = (yd - n)n or (ny - x)d = n^2.

    So d divides m^2 and n^2,
    d is a common divisor of m and n,
    d must be 1,
    gcd(mn, m+n) = 1.

    Hope this helps.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2012
    From
    United Kingdom
    Posts
    4
    Thanks
    1

    Re: Greatest Common Divisor

    I'm not sure I follow:
    You have (my - x)d = m^2 and you say d divides m^2. How do we know that (my-x) does not divide m^2?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2012
    From
    Jacksonville, FL
    Posts
    30
    Thanks
    4

    Re: Greatest Common Divisor

    They both do. Remember,

    ab = c implies that both a and b are divisors of c.

    We didn't need to show that (my-x) divides m^2, so it wasn't mentioned.

    Hope that makes it more clear.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2012
    From
    United Kingdom
    Posts
    4
    Thanks
    1

    Thumbs up Re: Greatest Common Divisor

    Many Thanks. That certainly makes it more clear.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2012
    From
    United Kingdom
    Posts
    4
    Thanks
    1

    Re: Greatest Common Divisor

    While the above is OK, it is rather long. I have come across the following solution which I think is rather neat.

    Consider a prime p which divides mn and m+n. From the first of these, p must divide m or n. From the second, if it divides m then it must also divide n, and conversely. Hence p divides both m and n. But there is no such prime since m and n are coprime. Hence no such p exists, so the two numbers are coprime.

    Regards - florian
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Nov 2012
    From
    india
    Posts
    8
    Thanks
    1

    Re: Greatest Common Divisor

    4 example problems of determining the greatest common factor of two numbers by factoring the 2 numbers first.
    Thanks from florian
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 05:45 AM
  2. Greatest Common Divisor.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 23rd 2009, 12:36 AM
  3. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 17th 2009, 07:16 PM
  4. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 4th 2008, 01:08 AM
  5. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 16th 2006, 02:56 PM

Search Tags


/mathhelpforum @mathhelpforum