# 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) $\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},\ldots,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},\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

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

Likewise, the first determination, though quite obvious, was

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

 $\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 $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)}\binom{\omega(n)}{i}=\sum_{i=0}^{\omega(n)}\binom{\omega% (n)}{i}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)}$ Ifmun1omeganThentaun2omegan 2013-03-22 18:18:41 2013-03-22 18:18:41 1and2and4 (20899) 1and2and4 (20899) 5 1and2and4 (20899) Corollary msc 11A25