# Show that $\omega * \mu$ is either 0 or 1.

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.