Define \(\varphi_2(n)\) to be the number of integers \(a \in \{0, \dotsc, n-1\} \) such that \(\gcd(a, n) = \gcd(a+1, n) = 1\). Show that if \(n = p_1^{e_1} \dotsm p_r^{e_r}\) is the factorization of \(n\) into primes, then \(\varphi_2(n) = n \prod_{i=1}^r (1 - \frac{2}{p_i}) \).

== Attempt ==

First, observe that \(\varphi_2(n) = p - 2 \) for every prime \(p\), since the integers \( 1, \dotsc, p - 2 \) and \( 1+1, \dotsc, p - 2 + 1 \) are not divisible by \(p\), and hence are relatively prime to \(p\).

Second, let \(p\) be a prime and \(e\) be a positive integer, we can see that \(\varphi_2(p^e) = p^{e-1}(p - 2) \). How ? The integers that are multiple of either \(p\) or \((p-1)\) but less than \(p^e\) are:

\( 0, p, 2p, \dotsc, (p^{e-1} - 1) \cdot p, \mspace10pt \text{and} \)

\( (p-1), 2(p-1), \dotsc, p^{e-1} \cdot (p-1)\)

of which there are precisely a total of \(2p^{e-1}\). Thus,

\(\varphi_2(p^e) = p^e - 2p^{e-1} = p^{e-1}(p - 2) \).

Third, it can be shown using Chinese remainder theorem that if \(\{n_i\}_{i=1}^k\) is a pairwise relatively prime family of positive integers, and let \(n := \prod_{i=1}^k n_i\), then

\( \varphi_2(n) = \prod_{i=1}^k \varphi_2(n_i) \)

which implies

\( \varphi_2(n) = \varphi_2(p_1^{e_1}) \dotsm \varphi_2(p_r^{e_r}) \).

Combining this with the result in step 2, we have:

\(\varphi_2(n) = \prod_{i=1}^r p_i^{e-1}(p_i - 2) = n \prod_{i=1}^r (1 - \frac{2}{p_i}) \)

\(\Box\)