How many divisors does $360$ have, and what do they add up to? Listing them works but is slow and easy to get wrong. With the prime factorization in hand, both questions have formulas.
Notation. $\tau(n)$ is the number of positive divisors of $n$ (also written $d(n)$), and $\sigma(n)$ is their sum. For $n = 12$: the divisors are $1, 2, 3, 4, 6, 12$, so $\tau(12) = 6$ and $\sigma(12) = 28$.
Formulas. If $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, then $$\tau(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1), \qquad \sigma(n) = \prod_{i=1}^{k} \left(1 + p_i + p_i^{2} + \cdots + p_i^{a_i}\right) = \prod_{i=1}^{k} \frac{p_i^{a_i + 1} - 1}{p_i - 1}.$$
Why it works
| $3^{0} = 1$ | $3^{1} = 3$ | $3^{2} = 9$ | |
|---|---|---|---|
| $2^{0} = 1$ | 1 | 3 | 9 |
| $2^{1} = 2$ | 2 | 6 | 18 |
| $2^{2} = 4$ | 4 | 12 | 36 |
| $2^{3} = 8$ | 8 | 24 | 72 |
Worked example: Counting divisors
- $360 = 2^{3} \cdot 3^{2} \cdot 5$.
- $\tau(360) = (3 + 1)(2 + 1)(1 + 1) = 4 \cdot 3 \cdot 2 = 24$.
Answer: $24$.
Worked example: Adding divisors
- $72 = 2^{3} \cdot 3^{2}$.
- $\sigma(72) = (1 + 2 + 4 + 8)(1 + 3 + 9) = 15 \cdot 13 = 195$.
- Check by adding the table's twelve entries: $1 + 2 + 3 + 4 + 6 + 8 + 9 + 12 + 18 + 24 + 36 + 72 = 195$.
Answer: $195$.
Worked example: Designing a number
- We need $(a_1 + 1)(a_2 + 1) \cdots = 12$. The ways to write $12$: $12$, $6 \cdot 2$, $4 \cdot 3$, $3 \cdot 2 \cdot 2$.
- Give the biggest exponent to the smallest prime: $2^{11} = 2048$, $\ 2^{5} \cdot 3 = 96$, $\ 2^{3} \cdot 3^{2} = 72$, $\ 2^{2} \cdot 3 \cdot 5 = 60$.
- The smallest is $60$.
Answer: $60$.
Common mistake
A pleasant consequence: $\tau(n)$ is odd exactly when $n$ is a perfect square. Divisors come in pairs $d$ and $n/d$, like $2$ and $36$ for $72$, and a pair collapses to a single divisor only when $d = n/d$, that is, $d^{2} = n$. In the formula, $\tau(n)$ is odd exactly when every $a_i + 1$ is odd, so every exponent $a_i$ is even.
Key idea