NT-B2-M10-P014 Когда \(\varphi(n)\mid n\)

Посмотрите на \(\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}\) и на количество нечётных простых делителей.

Для целости \(\frac{n}{\varphi(n)}\) произведение \(\prod_{p\mid n}\frac{p}{p-1}\) должно быть целым. Каждый нечётный простой \(p\) даёт в знаменателе чётный множитель \(p-1\). В числителе произведения простых может быть только один множитель \(2\), если \(2\mid n\). Поэтому нечётных простых делителей не больше одного. Если нечётный простой \(p\) есть, то нужно, чтобы \(p-1\mid 2\), значит \(p=3\), и обязательно \(2\mid n\). Следовательно решения: \(n=1\), \(n=2^a\) при \(a\ge 1\), и \(n=2^a3^b\) при \(a,b\ge 1\). Все они легко проверяются.

Олимпиадная задача на ограничение множества простых делителей.