1. ## Euler phi-function

Let n be a positive integer having k distinct odd prime divisors. Prove that 2^k divides Euler phi-function(n).

2. Suppose $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\cdot\cdot p_k^{\alpha_k}$ where $p_i \neq 2$.

Then $\phi(n) = \phi(p_1^{\alpha_1})\cdot\phi(p_2^{\alpha_2})\cdot \cdot\cdot\phi(p_k^{\alpha_k})$.

Note that $\phi(p_i^{\alpha_i})=p_i^{\alpha_i-1}\cdot (p_i-1)$.

So we have $2 \mid p_i-1 \; \forall i \implies 2^k \mid \phi(n)$.