Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have to proof the following statement:

Let $S(n)$ the number of (positive) squarefree divisors of $n$, thus $S(n)=\sum \limits_{d \mid n} \left|{\mu(d)}\right|$, and let $\omega$ be the number of different prime integers of $n$. Then follows $S(n)=2^{\omega(n)}$.

Any help is appreciated.


Ok, I'll try the proof:

Let $n=p_{1}^{e_1} * p_{2}^{e_2}* \ldots *p_{k}^{e_k}$

Both functions are multiplicative, so we get the following

$\sum \limits_{d \mid p_{1}^{e_1}} \left| {\mu(d)} \right|=\left| 1+\mu(p_{1}^{e_1}) \right|$

$\sum \limits_{d \mid p_{2}^{e_2}} \left| {\mu(d)} \right|=\left| 1+\mu(p_{2}^{e_2}) \right|$


$\sum \limits_{d \mid p_{k}^{e_k}} \left| {\mu(d)} \right|=\left| 1+\mu(p_{k}^{e_k}) \right|$

When $p_i$ is squarefree, we get for each addend as result a $"2"$. So we have $2^k$ possibilities. If $p_i$ is not squarefree, the addend is $"1"$. That finishs the proof.

share|cite|improve this question
What do you mean by square free integers of $n$? Do you mean divisors of $n$? – user17090 Nov 19 '11 at 18:59
Yes, exactly. Sorry, I'll edit it. – ulead86 Nov 19 '11 at 19:00
I took the liberty of editing the title. – Gerry Myerson Nov 19 '11 at 23:22
Mostly so far not useful. – André Nicolas Nov 20 '11 at 4:34
How I have to improve? – ulead86 Nov 20 '11 at 11:07
up vote 3 down vote accepted

Hint: Line up all the prime divisors of $n$, say $p_1$, $p_2$, and so on up to $p_k$, in a row. To make a square-free divisor of $n$, stop in front of each prime and say YES or NO (if you prefer, say $1$ or $0$). All NO gives you the square-free divisor $1$. All YES gives you $p_1p_2\cdots p_k$. Some YES some NO gives you stuff in between. How many ways can you make your decisions?

Another way: Note that $\sum_{d|n}|\mu(n)|$ and $2^{\omega(n)}$ are both multiplicative functions of $n$. So to verify they are the same, we need only verify equality at $1$ and at prime powers. For any prime $p$, and any $e>0$, if $n=p^e$, each of our functions is $2$ at $n$. This proof is probably the intended one.

share|cite|improve this answer
Ok thanks for the hints. I tried a proof above, perhaps someone can have a look :-) – ulead86 Nov 19 '11 at 22:26
Hm, where should I start if my try isn't enough? – ulead86 Nov 21 '11 at 17:56
For your proof, you might want to explain why each side is multiplicative. For example, $\mu$ is (standard), so therefore $|mu|$ is, therefore $\sum_{d|n}|mu|$ is (basic multiplicativity fact). Then explain clearly (you didn't) why $\sum{d|p^e}|\mu(d)|=2$. (Get $1$ for $d=1$, $1$ for $d=p$, the rest of the terms you are adding up are $0$'s.) All of your displayed formulas are technically incorrect. And you only need to show equality of $S(n)$ and $2^{\omega(n)}$ at $n$ a prime power. Maybe try to understand first proof. There are $2^k$ sequences of length $k$ made up of Y and/or N. – André Nicolas Nov 21 '11 at 18:19

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.