Лемма. Пусть $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}$.

Ответ задачи отсутствует