Number of divisors with even number of prime factors

Question

I'm stuck with the following train of thought. Let $$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$$ s.t. the number of divisors is $$d(n)=(a_1+1)(a_2+1)\cdots(a_k+1)\,.$$ Now I want to find the size of the subset of divisors with only an even number of prime factors. Maybe there is a trivial thought, but currently I try to visualize it like this $$\underbrace{\bullet \bullet\cdots\bullet}_{a_1\times p_1} \quad \underbrace{\bullet \bullet\cdots\bullet}_{a_2\times p_2} \quad \cdots \quad \underbrace{\bullet \bullet\cdots\bullet}_{a_k\times p_k}$$ where in total there are $a=a_1+a_2+...+a_k$ dots. There is exactly 1 possibility to choose no prime factor and $k$ possibilities to choose $1$ prime factor (which is odd however). Now my idea was to count the number of divisors with $m$ prime factors and then sum over all even $m$. If all primes were distinct, then this would amount for $\binom{a}{m}=\binom{k}{m}$, which is the number of ways to choose $m$ primes out of $a$ distinct primes. In the current setup however, not all $a$ primes are distinct. How do I divide out the overcounting?

Answer 1

Let $$ f(x) = \prod_{i=1}^k 1 + x+ \dots +x^{a_i}. $$ The quantity you want is the sum of the even coefficient of the polynomial $f(x)$, that is $d = (f(1) + f(-1))/2$. So, while $f(1)$ is the number of divisors $d(n)$, $f(-1)$ is either $1$ or $0$. Since $d$ must be integer anyway, the only choice is $d = \lceil d(n)/2\rceil$.

Answer 2

Let $\Omega(n)$ denote the number of prime factors of $n$ counted with multiplicities. Then we have

$$ \sum_{\substack{m|d\\\Omega(m)\text{ even}}}1=\sum_{m|n}{1+(-1)^{\Omega(m)}\over2}=\frac12d(n)+\frac12\sum_{m|n}(-1)^{\Omega(m)}=\frac12d(n)+\frac12\prod_{i=1}^k{1-(-1)^{a_i}\over2}. $$

Since the right most term is always within $[0,1/2]$, we conclude that

$$ \sum_{\substack{m|d\\\Omega(m)\text{ even}}}1=\left\lceil d(n)\over2\right\rceil. $$