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)$.


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)$.

  • 2
    $\begingroup$ That's a good start. The next step would then be multiplicativity. $\endgroup$ Commented Aug 19, 2013 at 17:48

2 Answers 2


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.


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .