Problem
NT-B2-M10-P019 A Power of Two in \(\varphi(n)\)
#19
★★★★★ Level 5 of 5
Let \(n>1\), and let \(\omega(n)\) be the number of distinct prime divisors of \(n\). Prove that \(2^{\omega(n)-1}\mid \varphi(n)\).
1001 Problems in Classical Number Theory (method inspiration) · Problem 532
Write \(\varphi(n)=\prod p^{a-1}(p-1)\) and count the even factors \(p-1\).
Let \(n=\prod_{i=1}^{r}p_i^{a_i}\), where \(r=\omega(n)\). Then \(\varphi(n)=\prod_{i=1}^{r}p_i^{a_i-1}(p_i-1)\). If none of the \(p_i\) is \(2\), then all \(p_i\) are odd, and each factor \(p_i-1\) is even; hence \(2^r\mid\varphi(n)\), so certainly \(2^{r-1}\mid\varphi(n)\). If \(2\mid n\), then among the remaining primes there are \(r-1\) odd ones, and their factors \(p_i-1\) give divisibility by \(2^{r-1}\). The claim follows.
A strong but clean problem on the structure of Euler's formula.