Maths Olympiad Prep

Library / /8 of 10

Number theory Difficulty 6.8 National Olympiad Prove it Mongolia

We say a rational number is good if it can be written as ab+ba\frac{a}{b} + \frac{b}{a} for some positive integers aa and bb.
(i) Show that any integer n4n \ge 4 can be written as the sum of some good numbers.
(ii) What is the minimum number of good numbers that n=57n = 57 can be written as the sum?

Solution

Answer: (ii) Three.
(i) 2=11+112 = \frac{1}{1} + \frac{1}{1} and 52=21+12\frac{5}{2} = \frac{2}{1} + \frac{1}{2} are good, thus 4=2+24 = 2 + 2 and 5=52+525 = \frac{5}{2} + \frac{5}{2} are sums of two good numbers. For n4n \ge 4, we can write n=2(k+2)n = 2(k+2) or n=2k+5n = 2k+5 with k0k \ge 0, thus nn is a sum of good numbers.

(ii) 57 is the sum of three good numbers:
57=(521+152)+(4526+2645)+(209+920)=(752+275)+(256+625)+(151+115). \begin{aligned} 57 &= \left(\frac{52}{1} + \frac{1}{52}\right) + \left(\frac{45}{26} + \frac{26}{45}\right) + \left(\frac{20}{9} + \frac{9}{20}\right) \\ &= \left(\frac{75}{2} + \frac{2}{75}\right) + \left(\frac{25}{6} + \frac{6}{25}\right) + \left(\frac{15}{1} + \frac{1}{15}\right). \end{aligned}
Now we show three is the minimum.
First suppose 57=ab+ba57 = \frac{a}{b} + \frac{b}{a} is good. We may assume (a,b)=1(a, b) = 1. We have a2+b2=57ab0(mod3)a^2 + b^2 = 57ab \equiv 0 \pmod{3} and thus ab0(mod3)a \equiv b \equiv 0 \pmod{3}, and this contradicts (a,b)=1(a, b) = 1.

Now suppose 57=ab+ba+cd+dc57 = \frac{a}{b} + \frac{b}{a} + \frac{c}{d} + \frac{d}{c} with (a,b)=(c,d)=1(a,b) = (c,d) = 1. Since (a2+b2,ab)=(c2+d2,cd)=1(a^2 + b^2, ab) = (c^2 + d^2, cd) = 1 and
(a2+b2)(cd)+(c2+d2)(ab)=57(ab)(cd), (a^2 + b^2)(cd) + (c^2 + d^2)(ab) = 57(ab)(cd),
we have abcdab | cd and cdabcd | ab. Thus ab=cdab = cd and a2+b2+c2+d2=57ab=57cda^2 + b^2 + c^2 + d^2 = 57ab = 57cd. Moreover, we have
(ab)2+(c+d)2=(a+b)2+(cd)2=a2+b2+c2+d20(mod3). (a-b)^2 + (c+d)^2 = (a+b)^2 + (c-d)^2 = a^2 + b^2 + c^2 + d^2 \equiv 0 \pmod{3}.
It follows ab0(mod3)a \equiv b \equiv 0 \pmod{3}, and this contradicts (a,b)=1(a,b) = 1. Hence at least three good numbers are needed to express 57 as their sum.

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.