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

Corollary. If $n$ is a squarefree positive integer with a given number of prime factors, then the total count of its divisors is a power of two, specifically, two raised to the number of prime factors. With $\mu$ being the Möbius function, $\omega$ being the number of distinct prime factors function, and $\tau$ the divisor function, we can write that if $\mu (n)={(-1)}^{\omega (n)}$ then $\tau (n)=2^{\omega (n)}$.

Since it is stipulated that $n$ is squarefree, the number of (nondistinct) prime factors function (http://planetmath.org/NumberOfNondistinctPrimeFactorsFunction) $\mathrm{\Omega }$ can be used instead of $\omega$.

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

Proof.

$n$ has $\omega (n)$ prime factors, which here are labelled $p_1,p_2,\mathrm{\dots },p_{\omega (n)}$ (they don’t necessarily have to be sorted, but it doesn’t hurt). This accounts for the prime divisors of $n$, therefore $\tau (n)$ must be at least $\omega (n)$. The semiprime divisors of $n$ are $p_1{p}_2,p_1{p}_3,\mathrm{\dots },p_1{p}_{\omega (n)},p_2{p}_3,\mathrm{\dots },p_2{p}_{\omega (n)},\mathrm{\dots }$ Basically, the number of ways to choose two prime factors from among $\omega (n)$ choices, which is the binomial coefficient

$$\left(\genfrac{}{}{0pt}{}{\omega (n)}{2}\right).$$

Likewise, the first determination, though quite obvious, was

$$\left(\genfrac{}{}{0pt}{}{\omega (n)}{1}\right)=\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:

$$\left(\genfrac{}{}{0pt}{}{\omega (n)}{\omega (n)}\right)=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 $n$ 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 $n$ with $\omega (n)$ prime factors, it is a simple matter of adding up row $\omega (n)$ of Pascal’s triangle:

$$\sum _{i=0}^{\omega (n)}\left(\genfrac{}{}{0pt}{}{\omega (n)}{i}\right)=\sum _{i=0}^{\omega (n)}\left(\genfrac{}{}{0pt}{}{\omega (n)}{i}\right)1^{\omega (n)-i}{1}^i={(1+1)}^{\omega (n)}=2^{\omega (n)},$$

exactly as the theorem stated. ∎

The consequences of the theorem are that the number 1 has one divisor: 1; a prime $p_1$ has two divisors: $1,p_1$; a semiprime has four divisors: $1,p_1,p_2,p_1{p}_2$; a sphenic number has eight divisors: $1,p_1,p_2,p_3,p_1{p}_2,p_2{p}_3,p_1{p}_2{p}_3$; a number with four prime factors has sixteen divisors; and so on and so forth.

Title	if $\mu (n)={(-1)}^{\omega (n)}$ then $\tau (n)=2^{\omega (n)}$
Canonical name	Ifmun1omeganThentaun2omegan
Date of creation	2013-03-22 18:18:41
Last modified on	2013-03-22 18:18:41
Owner	1and2and4 (20899)
Last modified by	1and2and4 (20899)
Numerical id	5
Author	1and2and4 (20899)
Entry type	Corollary
Classification	msc 11A25