I'm trying to solve the following problem:

Define $v(1) = 0$ and for $n \gt 1$ let $v(n)$ be the number of distinct prime factors of n. Let $f=\mu*v$ and prove that $f(n)$ is either $0$ or $1$.

Here's what I've done:

We know that $f(n) = \Sigma_{d|n}v(\frac{n}{d})\mu(d)$, and since $\mu(d) = 0$ when $d$ is not square-free, we need only consider $d$ of the form $p_1p_2...p_k$ for $p_i$ prime factors of $n$.

Now we write $n = p_1p_2...p_rp_{r+1}^{\alpha_1}...p_{m}^{\alpha_{m-r}}$, where $\alpha_i\gt1$ $\forall m-r\geq i\geq1$. Now we see that the value of $v(n/d)$ is only influenced by the number of prime divisor $p_i$ of $d$ such that $r\geq i\geq 1$, that is if $d = p_{s_1}p_{s_2}...p_{s_q}$ where $k$ of these primes are between $1$ and $r$ then $v(n/d) = v(n)-k$.

Then the problem is now a combinatorial problem. I'll now split up the sum $\Sigma_{d|n}v(\frac{n}{d})\mu(d)$ into partitions based on the magnitude of $v(\frac{n}{d})\mu(d)$. For example if the magnitude is $v(n)$ this can occur when the prime divisors of $d$ all have subscript larger than $r$, however the sign of $v(\frac{n}{d})\mu(d)$ varies by the number of prime divisors of $d$ and so restricting the sum to the $d$ which only output of magnitude $v(n)$ we get $v(n) \Sigma _{k = 1}^{m-r}(-1)^k {{m-r}\choose{k}}$ and so overall we get:

$$\Sigma_{d|n}v(\frac{n}{d})\mu(d) =v(n) \Sigma _{k = 1}^{m-r}(-1)^k {{m-r}\choose{k}} +\Sigma_{s = 1}^{r}(-1)^{s} (v(n)-s) \Sigma _{k = 0}^{m-r}(-1)^k {{m-r}\choose{k}}.$$ however note that $\Sigma _{k = 0}^{m-r}(-1)^k {{m-r}\choose{k}} = (1-1)^{m-k} = 0$ and so we get that $$\Sigma_{d|n}v(\frac{n}{d})\mu(d) =v(n) \Sigma _{k = 1}^{m-r}(-1)^k {{m-r}\choose{k}} = -v(n)$$

which certainly isn't the right answer.

Does someone have any idea where I could've went wrong here? I'm also certain there must be a cleaner way to do this.


Put $$F(n)=\left\{ \begin{align}1, \quad &n \> \text{is prime} \\ 0, \quad & n\> \text{is not prime}\end{align}\right.$$

Notice that $v(n)=\sum_{d|n}F(d)$, so by the Möbius inversion formula, we get $f=F$, so the assertion.

  • $\begingroup$ ohh that's quite neat. Thanks a lot $\endgroup$ – H_Hassan Dec 12 '16 at 14:20

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.