|
|
 |
Условие
Некоторые из чисел 1, 2, 3, ..., $n$ покрашены в красный цвет так, что выполняется условие: если для красных чисел $a, b, c$ (не обязательно различных) $a(b - c)$ делится на $n$, то $b = c$.
Докажите, что красных чисел не больше чем φ($n$).
Решение
Лемма. Пусть $D$ – некоторое множество различных простых делителей числа $n$. Количество натуральных чисел, не превосходящих $n$ и не кратных ни одному числу из $D$, равно $n$ $\Pi_{p\in D} \left(1-\frac{1}{p}\right)$.
Доказательство. Раскрыв скобки, получаем формулу включения-исключения.
Пусть красных чисел больше φ($n$). Тогда некоторые красные числа имеют с $n$ общий простой делитель. Пусть $q$ – наибольшее из таких простых и $a$ – красное число, кратное $q$. Для противоречия достаточно найти различные красные числа $b$ и $c$, сравнимые по модулю $\frac{n}{q}$, а для этого достаточно показать, что φ($n$) не меньше количества возможных остатков красных чисел по модулю $\frac{n}{q}$.
Пусть $D$ – множество всех простых делителей числа $n$, а $D'$ – множество его простых делителей, превосходящих $q$. Красные числа не делятся на числа из $D'$, поэтому и остатки от деления красных чисел на $\frac{n}{q}$ тоже не делятся на числа из $D'$.
По лемме φ($n$) = $n$ $\Pi_{p\in D} \left(1-\frac{1}{p}\right)$, а указанное количество остатков не больше чем $\frac{n}{q}$ $\Pi_{p\in D, p > q} \left (1 - \frac{1}{p}\right)$. После сокращений приходим к неравенству $q - 1 \geqslant \Pi_{p\in D, p < q}$ $\frac{p}{p-1}$, которое верно, поскольку $q - 1 = \frac{q-1}{q-2}\cdot\frac{q-2}{q-3}\cdot...\cdot\frac{3}{2}\cdot\frac{2}{1}$.
Замечания
12 баллов
