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:

  1. $\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}$.
  2. 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.