8. Let's call the efficiency of a natural number $n$ the fraction of all natural numbers from 1 to $n$ inclusive that have a common divisor with $n$ greater than 1. For example, the efficiency of the number 6 is $\frac{2}{3}$.

a) Does there exist a number with an efficiency greater than $80\%$? If so, find the smallest such number.

b) Does there exist a number with the maximum efficiency (i.e., not less than the efficiency of any other number)? If so, find the smallest such number.
Solution. Let's move on to studying inefficiency (1 minus efficiency). From the formula for Euler's function, it follows that it is equal to $\frac{p_{1}-1}{p_{1}} \cdot \ldots \frac{p_{k}-1}{p_{k}}$, where $p_{1}, \ldots, p_{k}$ are all distinct prime divisors of $n$. Then, by adding a new prime factor, we can increase the efficiency, so the answer in part (b) is "no".

The smallest number with an efficiency greater than $80\%$ is $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 30030$. Its efficiency is $1 - \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} \cdot \frac{6}{7} \cdot \frac{10}{11} \cdot \frac{12}{13} = \frac{809}{1001}$. We will prove that it is more efficient than all smaller numbers. Indeed, the presence of a prime factor with a power higher than one does not affect the efficiency, so the sought number has all factors in the first power. If the factors are not consecutive primes, then replacing one of the primes with a smaller one will increase the efficiency. Therefore, "efficiency records" can only be set by numbers of the form "the product of the first few primes"; but the efficiency of the number $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11$ is too low.

Criteria. Part (a) is scored 5 points, part (b) - 2 points.

![](https://cdn.mathpix.com/cropped/2024_05_06_e7d4d34b1ed44a375315g-5.jpg?height=279&width=297&top_left_y=109&top_left_x=157)

International Mathematical Olympiad

«Formula of Unity» / «The Third Millennium»

Year 2022/2023. Qualifying round

## Problems for grade R10

Each task is assessed at 7 points. Some problems have their own criteria (printed in gray).