3
$\begingroup$

If an integer $n>1$ has prime factorization $n=p_1^{k_1}p_2^{k_2}p_3^{k_3}\cdots p_r^{k_r}$ which of the following are true?

  1. $\sum_{d|n}\mu(d)\tau(d)=1$
  2. $\sum_{d|n}\mu(d)\tau(d)=p_1p_2\cdots p_r$
  3. $\sum_{d|n}\frac{\mu(d)}{d}=\sum_{i=1}^{r}\left( 1-\frac{1}{p_i}\right)$
  4. $\sum_{d|n}\mu(d)d=\prod_{i=1}^{r}(1-p_i)$

using $\phi(n)=n\sum_{d|n}\frac{\mu(d)}{d}$ I can show that 3 is not true. But for the rest I don't have any idea. I think we have to use Mobius Inversion formula, but don't know how? Any help please. Thanks.

$\endgroup$
2
  • $\begingroup$ Well, 1. and 2. can't both be true, can they? So why not plug in your favorite value of $n$, you'll eliminate at least one of the alternatives. In other words, don't just sit there – try something! $\endgroup$ Feb 16, 2017 at 6:17
  • $\begingroup$ Yes @GerryMyerson I am trying. Actually I was thinking of proving them, but completely forgot about trial and error method. Let me check. $\endgroup$ Feb 16, 2017 at 6:21

1 Answer 1

1
$\begingroup$

For a full explanation:

1 and 2: The only nonzero terms of $\sum_{d|n}\mu(d)\tau(d)$ come from $d$ being a product of distinct primes. There are $\binom rs$ divisors which are a product of $s$ distinct primes, and each of these contributes $(-1)^s2^s$. So $$\sum_{d|n}\mu(d)\tau(d)=\sum_{s=0}^r\binom rs(-2)^s=(1-2)^r=(-1)^r.$$

3: as you say, $\phi(n)=n\sum_{d|n}\frac{\mu(n)}d$ gives the RHS as the product of those terms, not the sum, so this is wrong.

4: Since $d\mu(d)$ is multiplicative, so is $\sum_{d|n}d\mu(d)$, and the RHS is also multiplicative, so it enough to check it is correct when $n=p^k$. In this case only the terms corresponding to $d=1$ and $d=p$ are nonzero, and this gives $f(p^k)=1-p$, as required.

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