Maths Olympiad Prep

Track / Stage 5 / 226 of 400 #826 of 1964

Problem 826

AIME late
Number theory Difficulty 5.5 Prove it India — Team Selection Test · India · 2008

Prove that there are infinitely many pairs (m,n)(m, n) of positive integers such that m<nm < n and (m+n)(m+n+1)mn\frac{(m+n)(m+n+1)}{mn} is an integer.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

If we take m=1m = 1, n=2n = 2, we see that (m+n)(m+n+1)mn=6\frac{(m+n)(m+n+1)}{mn} = 6. (Or we can start with m=2m = 2, n=3n = 3 as well.)

Suppose we have some pair (m,n)(m, n) of positive integers such that m<nm < n and
(m+n)(m+n+1)mn=k \frac{(m+n)(m+n+1)}{mn} = k
is an integer. This may be written in the form
nk=m+2n+1+n(n+1)m nk = m + 2n + 1 + \frac{n(n+1)}{m}
Thus n(n+1)m\frac{n(n+1)}{m} is also an integer, say equal to ll. Observe that
(n+l)(n+l+1)=(n+n(n+1)m)(n+1+n(n+1)m)=l(m+n+1)(m+n)m2. \begin{aligned} (n+l)(n+l+1) &= \left(n + \frac{n(n+1)}{m}\right) \left(n + 1 + \frac{n(n+1)}{m}\right) \\ &= \frac{l(m+n+1)(m+n)}{m^2}. \end{aligned}
Thus
(n+l)(n+l+1)nl=(m+n)(m+n+1)mn=k. \frac{(n+l)(n+l+1)}{nl} = \frac{(m+n)(m+n+1)}{mn} = k.
Moreover lm=n(n+1)>n2>nmlm = n(n+1) > n^2 > nm showing that l>nl > n. Hence (m,n)(n,l)(m, n) \neq (n, l). Thus starting with the pair (1,2)(1, 2), we can generate new pair (2,6)(2, 6) and the process may be continued indefinitely.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.