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

• Mar 10th 2011, 10:23 PM
ahm0605
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.
• Mar 11th 2011, 05:56 AM
Opalg
Quote:

Originally Posted by ahm0605
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.
• Mar 11th 2011, 05:56 AM
Amer
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
• Mar 11th 2011, 06:08 AM
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 .
• Mar 11th 2011, 06:09 AM
• Mar 11th 2011, 06:31 AM
emakarov
Quote:

Originally Posted by Amer
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.
• Mar 11th 2011, 06:43 AM
Quote:

Originally Posted by emakarov
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 .
• Mar 11th 2011, 06:59 AM
Amer
Quote:

Originally Posted by emakarov
Not necessarily. For a = 3 and b = 6, (a + 1) / b + (b + 1) / a = 3.

I think Opalg's solution is correct.

opsss
• Mar 11th 2011, 04:26 PM
ahm0605
but how do i know d^2 is not greater than a + b. that is where i got stuck on. appreciate everybodies insight.
• Mar 11th 2011, 09:05 PM
Amer
$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
• Mar 12th 2011, 07:16 PM
ahm0605
Thank you guys for all the help