if μ(n)=(-1)ω(n) then τ(n)=2ω(n)

Corollary. If n is a squarefreeMathworldPlanetmath positive integer with a given number of prime factorsMathworldPlanetmath, then the total count of its divisorsMathworldPlanetmathPlanetmathPlanetmath is a power of two, specifically, two raised to the number of prime factors. With μ being the Möbius functionMathworldPlanetmath, ω being the number of distinct prime factors function, and τ the divisor functionDlmfDlmfMathworldPlanetmath, we can write that if μ(n)=(-1)ω(n) then τ(n)=2ω(n).

Since it is stipulated that n is squarefree, the number of (nondistinct) prime factors function (http://planetmath.org/NumberOfNondistinctPrimeFactorsFunction) Ω can be used instead of ω.

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


n has ω(n) prime factors, which here are labelled p1,p2,,pω(n) (they don’t necessarily have to be sorted, but it doesn’t hurt). This accounts for the prime divisorsPlanetmathPlanetmath of n, therefore τ(n) must be at least ω(n). The semiprime divisors of n are p1p2,p1p3,,p1pω(n),p2p3,,p2pω(n), Basically, the number of ways to choose two prime factors from among ω(n) choices, which is the binomial coefficientDlmfDlmfMathworldPlanetmath


Likewise, the first determination, though quite obvious, was


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 ω(n) factors, which is again obvious:


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 productPlanetmathPlanetmath 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 ω(n) choices, and that’s the 1 in the leftmost column of row ω(n) in Pascal’s triangle. So to count the number of divisors of a squarefree number n with ω(n) prime factors, it is a simple matter of adding up row ω(n) of Pascal’s triangle:


exactly as the theorem stated. ∎

The consequences of the theorem are that the number 1 has one divisor: 1; a prime p1 has two divisors: 1,p1; a semiprime has four divisors: 1,p1,p2,p1p2; a sphenic numberMathworldPlanetmath has eight divisors: 1,p1,p2,p3,p1p2,p2p3,p1p2p3; a number with four prime factors has sixteen divisors; and so on and so forth.

Title if μ(n)=(-1)ω(n) then τ(n)=2ω(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