# Proof: $S(n)=2^{\omega(n)}$ where $S(n)$ is the number of squarefree divisors of n

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

$\vdots$

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

-
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

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