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