Tau Function - Number of Positive Divisors

Theorem

Let $n$ be an integer such that $n \ge 2$, with prime decomposition $n = p_1^{k_1} p_2^{k_2} \ldots p_r^{k_r}$.

Let $\tau \left({n}\right)$ be the tau function of $n$.

Then:

$\displaystyle \tau \left({n}\right) = \prod_{j=1}^r \left({k_j + 1}\right)$

Proof

We have:

$d \backslash n \implies \forall i: 1 \le i \le r: d = p_1^{l_1} p_2^{l_2} \ldots p_1^{l_1}, 0 \le l_i \le k_i$

For each $i$, there are $k_i+1$ choices for $l_i$, making $\left({k_1 + 1}\right) \left({k_2 + 1}\right) \cdots \left({k_r + 1}\right)$ choices in all.

By the Fundamental Theorem of Arithmetic and hence the uniqueness of prime decomposition, each of these choices results in a different number, therefore a distinct divisor.

$\blacksquare$

Alternatively, the result follows immediately from Tau of Power of Prime and Tau Function is Multiplicative‎.

$\blacksquare$

Sources

• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 24 \beta$