Maths Olympiad Prep

Library / /8 of 27

, 2008

Number theory Difficulty 5.5 AIME, harder Prove it India

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.

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.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.