Maths Olympiad Prep

Library / /2 of 9

, 2013

Number theory Difficulty 5.7 AIME, harder Prove it Japan

Suppose the least common multiple of three positive integers xx, yy, zz is 21002100. What is the minimum possible value that the sum x+y+zx + y + z can take?

Solutions — 2

Solution 1

44
Since 2100=2235272100 = 2^2 \cdot 3 \cdot 5^2 \cdot 7, if we take x=52=25x = 5^2 = 25, y=7y = 7, z=223=12z = 2^2 \cdot 3 = 12, then the least common multiple of xx, yy, zz is 21002100 and we get x+y+z=44x + y + z = 44.

Now let us show that 4444 is the desired minimum value. Assume that the least common multiple of xx, yy, zz is 21002100, and x+y+z<44x + y + z < 44 is satisfied. Then, at least one of xx, yy, zz must be a multiple of 525^2. By symmetry we may assume without loss of generality that one such number is xx. Since 252>442 \cdot 5^2 > 44, we must have x=52=25x = 5^2 = 25. Then, we see that y+z<19y + z < 19, and among yy and zz, we must have a multiple of 222^2, a multiple of 33 and a multiple of 77. By symmetry we may assume that yy is a multiple of 77. Then, since 227>192^2 \cdot 7 > 19 and 37>193 \cdot 7 > 19, we see that yy can be a multiple neither of 222^2 nor of 33. Therefore, we see that zz must be a multiple of 223=122^2 \cdot 3 = 12. But then, we get x+y+z25+7+12=44x + y + z \ge 25 + 7 + 12 = 44, which shows that it is impossible to have x+y+z<44x + y + z < 44, and this establishes the claim that 4444 is the desired minimum value.

Solution 2

Since 2100=2235272100 = 2^2 \cdot 3 \cdot 5^2 \cdot 7, if we take x=52=25x = 5^2 = 25, y=7y = 7, z=223=12z = 2^2 \cdot 3 = 12, then the least common multiple of xx, yy, zz is 21002100 and we get x+y+z=44x+y+z = 44.

Now let us show that 4444 is the desired minimum value. Assume that the least common multiple of xx, yy, zz is 21002100, and x+y+z<44x+y+z < 44 is satisfied. Then, at least one of xx, yy, zz must be a multiple of 525^2. By symmetry we may assume without loss of generality that one such number is xx. Since 252>442 \cdot 5^2 > 44, we must have x=52=25x = 5^2 = 25. Then, we see that y+z<19y+z < 19, and among yy and zz, we must have a multiple of 222^2, a multiple of 33 and a multiple of 77. By symmetry we may assume that yy is a multiple of 77. Then, since 227>192^2 \cdot 7 > 19 and 37>193 \cdot 7 > 19, we see that yy can be a multiple neither of 232^3 nor of 33. Therefore, we see that zz must be a multiple of 223=122^2 \cdot 3 = 12. But then, we get x+y+z25+7+12=44x+y+z \ge 25+7+12 = 44, which shows that it is impossible to have x+y+z<44x+y+z < 44, and this establishes the claim that 4444 is the desired minimum value.

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.