Olympiad Maths Prep

Library / /8 of 14

Number theory Difficulty 8.0 National olympiad, round 2 Prove it Romania

Let nn be a positive integer, and let a1,,ana_1, \dots, a_n be pairwise distinct positive integers. Show that
k=1n1[a1,,ak]<4, \sum_{k=1}^{n} \frac{1}{[a_1, \dots, a_k]} < 4,
where [a1,,ak][a_1, \dots, a_k] is the least common multiple of the integers a1,,aka_1, \dots, a_k.

Solution

Since the number of positive divisors of a positive integer mm does not exceed 2m2\sqrt{m}, and a1,,aka_1, \dots, a_k are pairwise distinct positive divisors of [a1,,ak][a_1, \dots, a_k], it follows that [a1,,ak]k2/4[a_1, \dots, a_k] \ge k^2/4. Consequently,
k=1n1[a1,,ak]=1a1+k=2n1[a1,,ak]1+k=2n4k2<1+4k=2n1k214=1+42(1312n+1)<113<4. \begin{aligned} \sum_{k=1}^{n} \frac{1}{[a_1, \dots, a_k]} &= \frac{1}{a_1} + \sum_{k=2}^{n} \frac{1}{[a_1, \dots, a_k]} \le 1 + \sum_{k=2}^{n} \frac{4}{k^2} < 1 + 4 \sum_{k=2}^{n} \frac{1}{k^2 - \frac{1}{4}} \\ &= 1 + 4 \cdot 2 \left( \frac{1}{3} - \frac{1}{2n+1} \right) < \frac{11}{3} < 4. \end{aligned}

Looking for a route rather than 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.