For positive integers $a$ and $b$, we know $\dfrac{a+1}{b} + \dfrac{b+1}{a}$ is also
a positive integer. Prove that $\gcd(a,b) \le \sqrt{a+b}$.
Using Bézout's lemma, we know that $\gcd(a, b) = sa + tb$. I want to prove that $(sa+tb)^2 \le a+b$. We know $ab\,|\,a(a+1) + b(b+1)$.
Therefore, $(sa + tb)^2 \le (sa)^2 + (tb)^2 + 2st(a(a+1)+b(b+1))$.
I'm not sure how can continue from here. Any ideas to continue, or for a better way to prove the statement?
Thanks in advance.
Best Answer
Hagen von Eitzen does not seem to want to explain his answer further, so I will attempt to do so here:
Suppose that $d|a$ and $d|b$. Then we have the following: \begin{align*} \frac{a+b}{d^2} &= \frac{a^2+a}{d^2}+\frac{b^2+b}{d^2}-\frac{a^2}{d^2}-\frac{b^2}{d^2} \\ &=\left(\frac{a+1}{b}+\frac{b+1}{a}\right)\cdot\frac{a}{d}\cdot\frac{b}{d}-\frac{a^2}{d^2}-\frac{b^2}{d^2} \end{align*}
The RHS is an integer by the hypothesis of the problem. The LHS is positive by the hypothesis of the problem. Thus we can safely conclude that $\frac{a+b}{d^2}\geq 1$ for all common divisors of $a$ and $b$, which is what we wanted to show.