Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.


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

share|improve this question
That's a good start. The next step would then be multiplicativity. –  Daniel Fischer Aug 19 '13 at 17:48

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.