Maths Olympiad Prep

Library / NZMO Round One /18 of 39

NZMO Round One

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 a⩽ba \leqslant b. So x⩾yx \geqslant y and 1x⩽1y\frac{1}{x} \leqslant \frac{1}{y} and thus
2y⩾1x+1y=12. \frac{2}{y} \geqslant \frac{1}{x} + \frac{1}{y} = \frac{1}{2}.
Therefore y⩽4y \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=12−1y=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=12−1y=0\frac{1}{x} = \frac{1}{2} - \frac{1}{y} = 0 which is not possible.

Case 3 y=3y = 3:
This implies 1x=12−1y=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=12−1y=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 a⩽ba \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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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