Consider positive integers $a$ and $b$, where $a \ge b$ and the sum $\frac{a+1}{b}+\frac{b+1}{a}$ is also an integer. Find the sum of all $a$ values less than $1000$ that meet this criteria.
For example, if $a=3$ and $b=2$, then $$\frac{a+1}{b}+\frac{b+1}{a} = \frac{3+1}{2}+\frac{2+1}{3} = 3$$ which is an integer and provides one legal value of $a$. The problem asks for all such values of $a \lt 1000$. I’m assuming that a particular $a$ suffices if there exists even one $b \le a$ that satisfies the condition.
This problem can be solved by simply writing a computer program that double-loops through the positive integers less than 1000, testing each case, however I’m wondering if there is a more general/abstract way to solve it.
Here are some thoughts … I’m not sure how helpful they are:
- $\frac{a+1}{b}+\frac{b+1}{a}$, which is an integer, can be rewritten as $\frac{a}{b}+\frac{b}{a}+\frac{1}{b}+\frac{1}{a}$.
- either the quotients $(a+1) \div b$ and $(b+1) \div a$ are each also integers, or their fractional parts add up to $1$.
We use a now-standard technique called Vieta jumping, which has a fascinating and surprisingly recent history.
Suppose $a^2 + a + b^2 + b = kab$ for some integer $k$. Then, writing this as a polynomial in $a$ with integer coefficients:
$$a^2 - (kb-1) a + (b^2+b) = 0,$$
we see that if $(a,b)$ is one of the roots of the above quadratic, then the other one is $c = (b^2+b)/a$, which is clearly positive. Furthermore, since the two roots sum to an integer, namely $kb-1$, then $c$ is necessarily a positive integer.
Now let's consider sizes. If $a>b$, then $a \ge b+1$ so $c = b(b+1)/a \le b$. So if $(a,b)$ is one solution to the problem, then either $a=b$ or $(b,c)$ is a smaller solution, with the same value of $k$. Since all values remain positive, they can only get smaller finitely many times, so eventually we must reach a solution where $a=b$.
The case where $a=b$ is very easy: we must have $k = 2 + 2/a$, so the only solutions of this type are $(1,1)$ with $k=4$ and $(2,2)$ with $k=3$.
Finally, since every solution eventually reduces to either $(1,1)$ or $(2,2)$ by the reduction process, we can recover all solutions by running the process in reverse, starting from $(1,1)$ and $(2,2)$:
$$(1,1) \leftarrow (2,1) \leftarrow (6,2) \leftarrow (21,6) \leftarrow \cdots $$ $$(2,2) \leftarrow (3,2) \leftarrow (6,3) \leftarrow (14,6) \leftarrow \cdots $$
The values grow exponentially, so it doesn't take long for either sequence to exceed $1000$.