Results 1 to 11 of 11

Math Help - Show that the greatest common divisor of a and b is not greater than sqrt(a + b)

  1. #1
    Newbie
    Joined
    Mar 2011
    Posts
    9

    Show that the greatest common divisor of a and b is not greater than sqrt(a + b)

    Hi i need help with a problem i've been stuck on.

    The natural numbers a and b are such that

    (a + 1)/b + (b +1)/a

    is an integer. Show that the greatest common divisor of a and b is not greater than sqrt(a + b).

    I'm really stuck on this and I keep going round in circles. cannot prove anything.

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

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by ahm0605 View Post
    The natural numbers a and b are such that

    (a + 1)/b + (b +1)/a

    is an integer. Show that the greatest common divisor of a and b is not greater than sqrt(a + b).
    Put it over a common denominator: \frac{a+1}b+\frac{b+1}a = \frac{a^2+a+b^2+b}{ab} is an integer, so a^2+a+b^2+b = kab for some integer k. Then a+b = kab-a^2-b^2, and the right side of that is divisible by  d^2, where d = \text{gcd}(a,b). Now you're practically there.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    since
    \frac{a+1}{b} + \frac{b+1}{a} is an integer that means

     b \mid a+1 \;\;and\;\; a \mid b+1

    but g.c.d(a,b) divides a and b that's obvious
    and g.c.d(a , a+1 ) = 1
    let g.c.d(a,b) = d
    since  b \mid a+1
    then  d \mid a+1
    but  d \mid a too
    so d=1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Dec 2010
    From
    Tétouan/Morocco
    Posts
    44
    well , if (a + 1)/b + (b +1)/a is a positive integer , we must have :
    b divides a+1 and a divides b+1
    let d be the greatest common divisor of a and b then d|a and d|b , hence , d| b+1 and d|b so d=1 .
    we must now show that sqrt(a+b) is greater than 1 which is true since a and b (must be) are positive integers i.e a>=1 and b>=1 by summing we get sqrt(a+b) >=sqrt(2)>1 .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Dec 2010
    From
    Tétouan/Morocco
    Posts
    44

    Smile

    sorry Amer , i didn't see your reply.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    Quote Originally Posted by Amer View Post
    since
    \frac{a+1}{b} + \frac{b+1}{a} is an integer that means

     b \mid a+1 \;\;and\;\; a \mid b+1
    Not necessarily. For a = 3 and b = 6, (a + 1) / b + (b + 1) / a = 3.

    I think Opalg's solution is correct.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Dec 2010
    From
    Tétouan/Morocco
    Posts
    44
    Quote Originally Posted by emakarov View Post
    Not necessarily. For a = 3 and b = 6, (a + 1) / b + (b + 1) / a = 3.

    I think Opalg's solution is correct.
    Ooops , you're right .
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Quote Originally Posted by emakarov View Post
    Not necessarily. For a = 3 and b = 6, (a + 1) / b + (b + 1) / a = 3.

    I think Opalg's solution is correct.
    opsss
    Last edited by Amer; March 11th 2011 at 07:29 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Mar 2011
    Posts
    9
    but how do i know d^2 is not greater than a + b. that is where i got stuck on. appreciate everybodies insight.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    a + b = kab - a^2 -b^2
    as opalag said the right side is divisible by g.c.d(a,b)^2 = d^2
    which means  d^2 \mid a+b
    so a+b is multiple of d^2
    which means a+b equal to d^2 or larger
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Mar 2011
    Posts
    9
    Thank you guys for all the help
    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 Advanced Algebra Forum
    Replies: 4
    Last Post: April 18th 2010, 03:16 PM
  3. Greatest Common Divisor.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 23rd 2009, 12:36 AM
  4. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 17th 2009, 07:16 PM
  5. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 25th 2008, 09:36 AM

Search Tags


/mathhelpforum @mathhelpforum