PlanetMath: if $\mu(n) = (-1)^{\omega(n)}$ then $\tau(n) = 2^{\omega(n)}$

Note that for the sake of simplicity in this particular application, 1 is not considered a prime number.

Proof.

has $\omega(n)$ prime factors, which here are labelled $p_1, p_2, \ldots , p_{\omega(n)}$ (they don't necessarily have to be sorted, but it doesn't hurt). This accounts for the prime divisors of

, therefore $\tau(n)$ must be at least $\omega(n)$ . The semiprime divisors of

are $p_1 p_2, p_1 p_3, \ldots , p_1 p_{\omega(n)}, p_2 p_3, \ldots , p_2 p_{\omega(n)}, \ldots$ Basically, the number of ways to choose two prime factors from among $\omega(n)$ choices, which is the binomial coefficient

$\displaystyle \binom{\omega(n)}{2}.$

Likewise, the first determination, though quite obvious, was

$\displaystyle \binom{\omega(n)}{1} = \omega(n).$

The binomial coefficients can be used to determine the count of divisors with 3 prime factors, 4 prime factors, etc., all the way up to $\omega(n)$ factors, which is again obvious:

$\displaystyle \binom{\omega(n)}{\omega(n)} = 1.$

This should be familiar, as these values can be looked up in Pascal's triangle.

So far we've only looked at the divisors of which are the product of one or more prime numbers. But every positive integer has 1 as a divisor, and since 1 has zero prime factors, we can also use Pascal's triangle to count 1 as a divisor thus: the number of ways to choose zero prime factors from among $\omega(n)$ choices, and that's the 1 in the leftmost column of row $\omega(n)$ in Pascal's triangle. So to count the number of divisors of a squarefree number with $\omega(n)$ prime factors, it is a simple matter of adding up row $\omega(n)$ of Pascal's triangle:

$\displaystyle \sum_{i = 0}^{\omega(n)} \binom{\omega(n)}{i} = \sum_{i = 0}^{\om... ...binom{\omega(n)}{i} 1^{\omega(n) - i}1^i = (1 + 1)^{\omega(n)} = 2^{\omega(n)},$

exactly as the theorem stated. $\qedsymbol$

The consequences of the theorem are that the number 1 has one divisor: 1; a prime

has two divisors:

; a semiprime has four divisors:

; a sphenic number has eight divisors:

; a number with four prime factors has sixteen divisors; and so on and so forth.