дискретная-математика - Функция Эйлера

См. аналогичную задачу здесь.

Тут надо рассуждать немного аккуратнее, потому что когда мы применяем формулу для нахождения самой $%\varphi(n)$%, то все степени в каноническом разложении рассматриваются полностью. Верно, что $%n$% делится на 15, и тогда есть множители 3 и 5, но мы заранее не знаем, в каких они степенях.

Эта трудность легко преодолевается, если использовать не саму формулу для $%\varphi(n)$%, а её следствие: $%\varphi(n)/n=(1-p_1)\ldots(1-p_r)$% для всех простых делителей числа. Тогда получится $%15(p_1-1)\ldots(p_r-1)=4p_1\ldots p_r$%. Значит, справа есть $%p_1=3$%, $%p_2=5$% -- всё в одном экземпляре (порядок нумерации сомножителей не важен).

Подставляя эти числа и упрощая, имеем $%2(p_3-1)\ldots(p_r-1)=p_3\ldots p_r$%. Отсюда следует, что справа есть $%p_3=2$%. Снова подставляем, сокращаем, и приходим к тому, что больше ничего остаться не могло (в противном случае левая часть меньше правой).

Таким образом, необходимое и достаточное условие состоит в том, что простыми делителями $%n$% являются в точности 2, 3 и 5. То есть у Вас ответ верный, только способ его получения нужно слегка подправить. И наименьшее значение, конечно, равно $%n=30$%.