Maths Olympiad Prep

Library / /18 of 41

Number theory Difficulty 5.5 AIME, harder Prove it New Zealand

Problem:
Find all triples (a,b,n)(a, b, n) of positive integers such that aa and bb are both divisors of nn, and a+b=n2a + b = \frac{n}{2}.

Solution

Solution:
Since aa and bb are both factors of nn, we can find positive integers xx and yy such that a=nxa = \frac{n}{x} and b=nyb = \frac{n}{y}. Then nx+ny=n2\frac{n}{x} + \frac{n}{y} = \frac{n}{2} so
1x+1y=12. \frac{1}{x} + \frac{1}{y} = \frac{1}{2}.
Without loss of generality assume aba \leqslant b. So xyx \geqslant y and 1x1y\frac{1}{x} \leqslant \frac{1}{y} and thus
2y1x+1y=12. \frac{2}{y} \geqslant \frac{1}{x} + \frac{1}{y} = \frac{1}{2}.
Therefore y4y \leqslant 4. So we try y=1,2,3,4y = 1, 2, 3, 4 one by one.

Case 1 y=1y = 1:
This implies 1x=121y=0\frac{1}{x} = \frac{1}{2} - \frac{1}{y} = 0 thus x=2x = -2. This doesn't work because aa (and therefore xx) must be positive.

Case 2 y=2y = 2:
This implies 1x=121y=0\frac{1}{x} = \frac{1}{2} - \frac{1}{y} = 0 which is not possible.

Case 3 y=3y = 3:
This implies 1x=121y=16\frac{1}{x} = \frac{1}{2} - \frac{1}{y} = \frac{1}{6} and thus x=6x = 6. This means that nn must be a multiple of 66. Now let n=6kn = 6k, and we get
a=nx=6k6=kandb=ny=6k3=2k. a = \frac{n}{x} = \frac{6k}{6} = k \qquad \mathrm{and} \qquad b = \frac{n}{y} = \frac{6k}{3} = 2k.
This yields the family of solutions (a,b,n)=(k,2k,6k)(a, b, n) = (k, 2k, 6k) where kk is any positive integer.

Case 4 y=4y = 4:
This implies 1x=121y=14\frac{1}{x} = \frac{1}{2} - \frac{1}{y} = \frac{1}{4} and thus x=4x = 4. This means that nn must be a multiple of 44. Now let n=4kn = 4k, and we get
a=nx=4k4=kandb=ny=4k4=k. a = \frac{n}{x} = \frac{4k}{4} = k \qquad \mathrm{and} \qquad b = \frac{n}{y} = \frac{4k}{4} = k.
This yields the family of solutions (a,b,n)=(k,k,4k)(a, b, n) = (k, k, 4k) where kk is any positive integer.

Remember that we assumed aba \leqslant b so we still need to swap the roles of aa and bb for our final answer. So in summary, the triples (a,b,n)(a, b, n) which satisfy the given equation are
(k,2k,6k), (2k,k,6k) and (k,k,4k) (k, 2k, 6k),\ (2k, k, 6k)\ \text{and}\ (k, k, 4k)
where kk is any positive integer.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.