Divisor Functions τ(n) and σ(n)

Counting and summing divisors from the prime factorization.

The idea

The divisor functions measure an integer through its divisors: $\tau(n)$ is the number of positive divisors of $n$, and $\sigma(n)$ is their sum. We can read both off the prime factorization.

A divisor of $n = p_{1}^{a_{1}} \cdots p_{k}^{a_{k}}$ chooses, for each prime $p_{i}$, an exponent from $0$ up to $a_{i}$, and because the factorization is unique, every divisor comes from exactly one such choice. Each prime offers $a_{i} + 1$ exponents, chosen independently of the others, so $\tau(n) = \prod_{i=1}^{k} (a_{i} + 1).$ For the sum, expand the product $\sigma(n) = \prod_{i=1}^{k} \left(1 + p_{i} + p_{i}^{2} + \cdots + p_{i}^{a_{i}}\right).$ Each term of the expansion picks one power of each prime, so the terms are precisely the divisors of $n$, each appearing once, and the product equals the divisor sum. The figure lays this out for $n = p^{a} q^{b}$: the choices form an $(a+1) \times (b+1)$ grid whose cells are exactly the divisors.

Both formulas carry one factor per prime, so both functions are multiplicative: when $\gcd(m, n) = 1$, the factorizations of $m$ and $n$ share no prime, and the value at $mn$ is the product of the values at $m$ and at $n$.

Ways to work on it

• Walkthrough. Build tau and sigma from exponents, and see multiplicativity.
• Practice. Compute tau or sigma from a factorization.
• Hardest. Use sigma to test the perfect-number condition.

Not sure where to start? Take the ten-question placement test.