Show that if $n$ is a positive integer with $r$ distinct odd prime factors, then $2^r \mid \varphi(n)$ 
Show that if $n$ is a positive integer with $r$ distinct odd prime factors, then $2^r \mid \varphi(n)$.

So I know that
$$\varphi(n) = \varphi(p_1^{a_1}\cdot p_2^{a_2} \cdots p_r^{a_r}) = (p_1^{a_1}-p_1^{a_1-1})(p_2^{a_2}-p_2^{a_2-1})\cdots(p_r^{a_r}-p_r^{a_r-1})=p_1^{a_1}(1-\frac{1}{p_1})p_2^{a_2}(1-\frac{1}{p_2}) \cdots p_r^{a_r}(1-\frac{1}{p_r}) = n\cdot (1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_r}).$$
and then I'm stuck. Any help would be appreciated!
 A: Let $n=p_1\cdots p_r$ then $\varphi(p_i) = p_i-1 = 2k_i$ thus $\varphi(n)=2k_1\cdots 2k_r = 2^r\cdot(k_1\cdots k_r)$
So $\frac{2^r\cdot(k_1\cdots k_r)}{2^r} = (k_1\cdots k_r) \Rightarrow 2^r \mid \varphi(n)$
A: Note that in your formula, each $p^a-p^{a-1}$ is the difference of two odd integers, and hence is even.  So you get a factor of 2 for each odd prime power that divides $n$.
A: $\varphi(ab)=\varphi(a)\varphi(b)$ when $gcd(a,b)=1$. $\varphi(p^k)=(p-1)[\text{stuff}]$, which is divisible by $2$. Combining these two facts gives the result, as each distinct prime factor introduces at least one multiple of $2$.
A: A counting argument. Definitely overkill.
In $R=\mathbb Z/n\mathbb Z$, Say that $x\sim y$ if $x^2=y^2$. Show $\sim$ is an equivalence relation.
Now if $x$ is a unit of $R$ and $x\sim y$ then show $y$ is a unit of $R$.
Finally, when $n$ is odd and $x$ is a unit, show that the $\sim$-equivalence class of $x$ has $2^r$ elements. (This is an application of the Chinese remainder theorem.)
So $\sim$ is an equivalence relation on the $\phi(n)$ units of $R$, and the equivalence classes all have size $2^r$.
