8
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ That's a good start. The next step would then be multiplicativity. $\endgroup$ – Daniel Fischer Aug 19 '13 at 17:48
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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