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$