Modification of Euler's Totient Function

Question

Problem

If $\phi_2(n)$ is the number of integers $a \in \{0, \dots, n-1\}$ such that $\gcd(a,n) = \gcd(a+1,n)=1$, I want to show that if $n = p_1^{e_1} \cdots p_r^{e_r}$ is the prime factorization of $n$, then $\phi_2(n) = n \prod_{i=1}^r(1-2/p_i)$.

Thoughts

I am not sure where to start with this, but looking at how Euler's totient function works would it be reasonable to start by taking $n = p^{e}$ so $n$ is just composed of a single prime raised to a power? In which case, I believe I would be showing that $\phi_2(p^e) = p^{e-1}(p-2)$.

This makes sense to me in the case that $e=1$ as given any prime $p$, every number in the set $\{0,\dots,p-1\}$ is relatively prime to $p$ but $0$ and so we would be excluding $2$ values from the $\phi_2(p)$, $\gcd(0,p) \neq \gcd(1,p)=1$ and $\gcd(p-1,p) = \gcd(p \equiv 0,p)=1$.

So for $p_e$, the $\phi_2(p^e)$ would count these $p-2$ instances where $\gcd(a,n) = \gcd(a+1,n)=1$ is true from $0,\dots p$ then from $p,\dots,p^2$ and so on giving $p^{e-1}$ counts of $\phi(p)$.

Answer 1

As a comment pointed out, note that your formula is multiplicative for products of different prime powers: I.e. if $n$ is a product of primes $p_1^{e_1} \cdots p_k^{e_k}$ and $m$ is a product of primes $q_1^{f_1} \cdots q_l^{f_l}$, and if all the $p_i$ and $q_j$ are all different, then you can check that your formula satisfies $\phi_2(mn) = \phi_2(m) \phi_2(n)$. Sometimes when this is the case, the best thing to do is to actually prove that the multiplicative relationship holds for any such $m,n$, because then the fact you proved the formula for prime powers automatically means the product holds for all numbers.

Answer 2

Think about probabilities.

Let $p$ be a prime that divides $n$, then the probability that, for $a$ randomly chosen out of $\{0,\dots,n-1\}$, both $a$ and $a+1$ are coprime to $p$ is just $1-\frac2p$.

By probabilistic reasoning, the probability that $a$ is coprime to all primes dividing $n$ is the product of these probabilities.

And hence, by the most basic principle of statistics, the total of desired numbers gives you this formula.