NT-B2-M10-P006 Когда \(\varphi(n)=n/2\)

Используйте \(\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}\).

Условие даёт \(\frac{n}{\varphi(n)}=2\). Если \(n\) имеет нечётный простой делитель \(p\), то в произведении есть множитель \(\frac{p}{p-1}\), и вместе с возможным множителем \(2\) от простого \(2\) получить ровно \(2\) нельзя. Значит единственный простой делитель \(n\) — \(2\). Поэтому \(n=2^a\), \(a\ge 1\). Все такие числа подходят, так как \(\varphi(2^a)=2^{a-1}\).

Классическая задача на отношение \(n/\varphi(n)\).