Show that if $n$ is divisible by $r$ distinct odd primes, then $2^r \mid \varphi(n)$, where $\varphi(n) := \lvert \mathbb{Z_n^*} \rvert$, which is the number of integers between $0$ and $n−1$ that are relatively prime to $n$.

== Attempt ==

Based on Theorem 2.11 of Shoup, we know that if $m = p_1^{e_1} \dotsm p_r^{e_r}$ is the factorization of $m$ into primes, then

$\displaystyle \varphi(m) = \prod_{i=1}^r p_i^{e_i-1}(p_i - 1)$

Given n is divisible by r distinct odd primes, $n = p_1^{e_1} \dotsm p_k^{e_k}$ for $k \ge r$. Furthermore, there must exist at least $r$ distinct odd $p_i$ in

$\displaystyle \varphi(n) = \prod_{i=1}^k p_i^{e_i-1}(p_i - 1)$

Since $(p_i - 1)$ is even when $p_i$ is odd, and there are at least $r$ of them, it follows $2^r \mid \varphi(n)$.

$\Box$