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