1. ## Euler's Phi Function

Prove that if the integer n has r distinct odd prime factors, then 2^r |
Ф(n).

2. Suppose $n \geq 3$ has $r$ odd prime factors.

By definition, we have: $\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 $p$ is prime, then $p-1$ is even. So for every odd prime dividing $n$, there is a corresponding even number (particularly $p-1$) that divides $\phi (n)$. Since there are $r$ odd primes, the conclusion follows.