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

Question

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!

Answer 1

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)$

Answer 2

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$.

Answer 3

$\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$.

Answer 4

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$.