Competition problem — Number theory

Library / /403 of 520

Number theory Difficulty 5.7 AIME, harder Prove it

1. Let $a, b$ be two given positive integers such that $\frac{a+1}{b}+\frac{b+1}{a}$ is an integer. Prove:
$(a, b) \leqslant \sqrt{a+b} .$
(20th All-Russian Mathematical Olympiad)

Solution

Notice that
$\frac{a+1}{b}+\frac{b+1}{a}=\frac{a^{2}+b^{2}+a+b}{a b} .$

Let $(a, b)=d$ . Then $d^{2} \mid a b$ . From $d^{2} \mid\left(a^{2}+b^{2}\right)$ , we get $d^{2} \mid(a+b)$ . Therefore, $a+b \geqslant d^{2}$ . Thus,
$(a, b) \leqslant \sqrt{a^{2}+b^{2}} .$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.