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

1. 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.

2. 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.

3. 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

4. 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 .

6. 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.

7. 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 .

8. 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

9. but how do i know d^2 is not greater than a + b. that is where i got stuck on. appreciate everybodies insight.

10. $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

11. Thank you guys for all the help