= Divisor function
{title2=$\tau(n)$}
{wiki}
The <divisor function> $\tau(n)=\sum_{d\mid n}1$ counts the positive <integer divisors> of a <positive integer> $n$. In particular $\tau(1)=1$, because $1$ has just one positive <integer divisor>. More generally the notation $\sigma_k(n)=\sum_{d\mid n}d^k$ gives $\tau=\sigma_0$ and the <sum-of-divisors function> $\sigma_1$. Thus the <divisor function> counts the positive <integer divisors>, while $\sigma_1$ adds their sizes. https://darijgrinberg.gitlab.io/floor.pdf[Darij Grinberg, MIT 18.781 lecture notes, Definition 2.1.2 and Theorem 2.1.6]{ref}
If the <prime factorization> is $n=\prod_{k=1}^r p_k^{a_k}$ with distinct <prime numbers> $p_k$ and positive exponents $a_k$, then
$$
\tau(n)=\prod_{k=1}^r(a_k+1).
$$
The short proof is a count: each positive <integer divisor> has a unique form $\prod_{k=1}^r p_k^{b_k}$, where $0\le b_k\le a_k$. There are $a_k+1$ choices at each <prime number>, and choosing them gives every positive <integer divisor> exactly once. For $n=1$ there are no <prime factors> and the product is $1$.
For $12=2^2\cdot3$, choose $i\in\{0,1,2\}$ and $j\in\{0,1\}$ to obtain $2^i3^j$. The six values are $1,2,4,3,6,12$; sorted, the positive <integer divisors> are $1,2,3,4,6,12$. Therefore $\tau(12)=(2+1)(1+1)=6$. The diagram makes the independent exponent choices visible.
\Image[/divisor-count-prime-exponents.png]
{title=The <prime factorization> $12=2^2\cdot3$ gives a three-by-two array of positive <integer divisors> $2^i3^j$, so the <divisor function> has $\tau(12)=6$}
This count is useful because a known <prime factorization> gives $\tau(n)$ without testing every smaller <positive integer> for <divisibility>. It also proves the <divisor function> is a <multiplicative function>: <coprime integers> have disjoint <prime factors>, so their exponent choices combine. For example $\tau(6)=4=\tau(2)\tau(3)$, but $\tau(4)=3\ne4=\tau(2)^2$, so it is not a <completely multiplicative function>. Equivalently, $\tau=\mathbf1*\mathbf1$ under <Dirichlet convolution>, counting <ordered pairs> of <positive integers> whose product is $n$.
Back to article page
