Maths Olympiad Prep

Library / /94 of 158

Number theory Difficulty 6.0 AIME, harder Prove it Estonia

a) Find the largest number that is the greatest common divisor of some four different two-digit numbers.

b) Find the largest number that is the least common multiple of some four different two-digit numbers.

Solution

a) Let dd be the greatest common divisor of some four different two-digit numbers. Since all these numbers are divisible by dd, the least possible candidates of these four numbers are dd, 2d2d, 3d3d, 4d4d. Hence 4d<1004d < 100, thus d24d \le 24. On the other hand, the greatest common divisor of 2424, 4848, 7272 and 9696 is 2424.

b) The numbers 9999, 9898, 9797, and 9595 are pairwise relatively prime, hence lcm(99,98,97,95)=99989795\text{lcm}(99, 98, 97, 95) = 99 \cdot 98 \cdot 97 \cdot 95. To show that this is the largest possible, consider four different two-digit numbers a1a_1, a2a_2, a3a_3, a4a_4; assume without loss of generality that a1>a2>a3>a4a_1 > a_2 > a_3 > a_4. If a495a_4 \le 95, then lcm(a1,a2,a3,a4)a1a2a3a499989795\text{lcm}(a_1, a_2, a_3, a_4) \le a_1 a_2 a_3 a_4 \le 99 \cdot 98 \cdot 97 \cdot 95. If a4=96a_4 = 96, then the four numbers can only be 9999, 9898, 9797, 9696, but lcm(99,98,97,96)=9998979623<99989795\text{lcm}(99, 98, 97, 96) = \frac{99 \cdot 98 \cdot 97 \cdot 96}{2 \cdot 3} < 99 \cdot 98 \cdot 97 \cdot 95.

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.