Maths Olympiad Prep

Library / /1 of 5

Number theory Difficulty 5.4 AIME, harder Prove it Taiwan

We call a positive integer superb if it is equal to the least common multiple of 1,2,,n1, 2, \ldots, n, where nn is a positive integer. Find all superb numbers xx, yy, zz satisfying x+y=zx + y = z.

A positive integer is superb if it is the least common multiple of 1,2,,n1, 2, \ldots, n for some positive integer nn. Find all superb x,y,zx, y, z such that x+y=zx + y = z.

Solution

All possible (x,y,z)(x, y, z) are x=y=[1,2,,2k1]x = y = [1, 2, \ldots, 2^k - 1] and z=[1,2,,2k]z = [1, 2, \ldots, 2^k], where kk is any positive integer and [][\ldots] denotes the least common multiple.

Clearly z>x,yz > x, y. Suppose x=[1,,a]x = [1, \ldots, a], y=[1,,b]y = [1, \ldots, b], and z=[1,,c]z = [1, \ldots, c], and without loss of generality assume aba \le b. Furthermore, without loss of generality let aa be maximal (that is, for any a>aa' > a we have x[1,,a]x \ne [1, \ldots, a']), let bb be maximal, and let cc be minimal. This necessarily guarantees that c>bc > b and yzy=xy \mid z - y = x, so x=yx = y and z=2xz = 2x. By this maximality and minimality, this means a=b=c1a = b = c - 1, and also 2v2(c)y2^{v_2(c)} \nmid y but 2v2(c)1y2^{v_2(c)-1} \mid y. This can only hold when cc is some power of 22 (otherwise 2v2(c)<c2^{v_2(c)} < c would divide yy.) Hence the solutions must be of the form x=y=[1,2,,2k1]x = y = [1, 2, \ldots, 2^k - 1] and z=[1,2,,2k]z = [1, 2, \ldots, 2^k], where kk is any positive integer. Substituting back to check shows this clearly holds. Q.E.D.

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 translated into English from zh; metadata (topic, difficulty) added by this project.