Prove that if the integer n has r distinct odd prime factors, then 2^r |
Ф(n).
Suppose $\displaystyle n \geq 3$ has $\displaystyle r$ odd prime factors.
By definition, we have: $\displaystyle \phi (n) = n \cdot \prod_{p \mid n} \left(\frac{p-1}{p}\right) = \frac{n}{\displaystyle \prod_{p \mid n} p} \cdot \prod_{p \mid n} (p-1)$
We know that the fraction is an integer and that since $\displaystyle p$ is prime, then $\displaystyle p-1$ is even. So for every odd prime dividing $\displaystyle n$, there is a corresponding even number (particularly $\displaystyle p-1$) that divides $\displaystyle \phi (n)$. Since there are $\displaystyle r$ odd primes, the conclusion follows.