Counting and Summing Divisors

How many divisors does 360 have?

You could list them. That works for 360. It fails when the number is large, or when the problem asks you to count divisors of $n^{10}$ without knowing $n$.

There's a formula. It comes entirely from prime factorization, and understanding why it works is more useful than the formula itself.

---

The number of divisors — $\tau(n)$

Theorem. If $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, then the number of positive divisors of $n$ is:

$\tau(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$

Why. Every divisor of $n$ has the form $d = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ where $0 \leq e_i \leq a_i$.

For each prime $p_i$, there are $a_i + 1$ choices for $e_i$ (from 0 to $a_i$). The choices are independent, so multiply.

Example. $360 = 2^3 \times 3^2 \times 5^1$.

$\tau(360) = (3+1)(2+1)(1+1) = 4 \times 3 \times 2 = 24$.

360 has 24 positive divisors.

Example. $\tau(p^k) = k+1$ for any prime $p$. The divisors are $1, p, p^2, \ldots, p^k$.

Example. $\tau(p) = 2$ for any prime $p$. Exactly two divisors: 1 and $p$. This is the definition of a prime.

---

Perfect squares and odd $\tau$

Theorem. $n$ is a perfect square $\iff$ $\tau(n)$ is odd.

Proof. Divisors pair up: if $d \mid n$, then $n/d \mid n$, and $d \neq n/d$ unless $d = \sqrt{n}$.

So divisors come in pairs except when $d = n/d$, i.e., $d^2 = n$. The count is odd iff $n$ is a perfect square. $\blacksquare$

Using the formula: $\tau(n) = \prod(a_i+1)$ is odd $\iff$ each $a_i+1$ is odd $\iff$ each $a_i$ is even $\iff$ $n$ is a perfect square.

---

The sum of divisors — $\sigma(n)$

Theorem. If $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, then the sum of all positive divisors of $n$ is:

$\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i+1} - 1}{p_i - 1} = \prod_{i=1}^{k} (1 + p_i + p_i^2 + \cdots + p_i^{a_i})$

Why. When you expand the product:

$(1 + p_1 + \cdots + p_1^{a_1})(1 + p_2 + \cdots + p_2^{a_2}) \cdots (1 + p_k + \cdots + p_k^{a_k})$

each term in the expansion is $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ with $0 \leq e_i \leq a_i$ — exactly the divisors of $n$. Summing all terms gives $\sigma(n)$. $\blacksquare$

Example. $\sigma(360)$ where $360 = 2^3 \times 3^2 \times 5$.

$\sigma(360) = (1+2+4+8)(1+3+9)(1+5) = 15 \times 13 \times 6 = 1170$

---

Multiplicativity

Both $\tau$ and $\sigma$ are multiplicative: if $\gcd(m, n) = 1$, then:

$\tau(mn) = \tau(m)\,\tau(n) \qquad \sigma(mn) = \sigma(m)\,\sigma(n)$

Why. The prime factorizations of $m$ and $n$ share no primes (since $\gcd(m,n)=1$). So the product formula for $\tau(mn)$ splits cleanly into the product for $\tau(m)$ times the product for $\tau(n)$.

This multiplicativity is why the formulas factor over primes — each prime contributes independently.

Common mistake. $\tau(mn) = \tau(m)\tau(n)$ requires $\gcd(m,n) = 1$. Without it: $\tau(4) = 3$ but $\tau(2)\tau(2) = 4$. They differ.

---

Perfect numbers

A positive integer $n$ is perfect if $\sigma(n) = 2n$ — it equals the sum of all its proper divisors (divisors excluding itself).

Examples: $6 = 1+2+3$ and $28 = 1+2+4+7+14$. Both perfect.

Euler's theorem on even perfect numbers. $n$ is an even perfect number $\iff$ $n = 2^{p-1}(2^p - 1)$ where $2^p - 1$ is prime (a Mersenne prime).

Proof sketch. Write $n = 2^{k} m$ with $m$ odd. Then $\sigma(n) = \sigma(2^k)\sigma(m) = (2^{k+1}-1)\sigma(m)$. Setting $\sigma(n) = 2n = 2^{k+1}m$ and solving forces $m = 2^{k+1}-1$ (a prime) and $k = p-1$.

Whether any odd perfect numbers exist is an open problem.

---

Worked problems

Problem 1. Find the number of divisors of $10^{10}$.

$10^{10} = 2^{10} \times 5^{10}$.

$\tau(10^{10}) = (10+1)(10+1) = 121$.

Problem 2. For how many values of $n \leq 100$ is $\tau(n)$ odd?

$\tau(n)$ is odd $\iff$ $n$ is a perfect square. Perfect squares $\leq 100$: $1, 4, 9, \ldots, 100$. That is 10 values.

Problem 3. Find all $n$ such that $\tau(n) = 2$.

$\tau(n) = 2 \iff n$ has exactly 2 divisors $\iff$ $n$ is prime. $\blacksquare$

Problem 4. Find $\sigma(2^k)$ and verify it equals $2^{k+1} - 1$.

$\sigma(2^k) = 1 + 2 + 4 + \cdots + 2^k = 2^{k+1} - 1$. (Geometric series.) ✓

Note: $\sigma(2^k)$ is always odd. So $2^k$ is never perfect — a perfect number requires $\sigma(n) = 2n$ which is even.

Problem 5. If $n = p^a q^b$ with $p, q$ distinct primes, find $\tau(n^2)$ in terms of $\tau(n)$.

$n^2 = p^{2a}q^{2b}$.

$\tau(n^2) = (2a+1)(2b+1)$.

$\tau(n) = (a+1)(b+1)$.

No clean relationship in general. But if $a = b$: $\tau(n) = (a+1)^2$ and $\tau(n^2) = (2a+1)^2$.

Problem 6. Find the sum of all divisors of 496. Is 496 perfect?

$496 = 16 \times 31 = 2^4 \times 31$.

$\sigma(496) = (1+2+4+8+16)(1+31) = 31 \times 32 = 992 = 2 \times 496$.

Yes, 496 is perfect. (And $31 = 2^5 - 1$ is a Mersenne prime, confirming Euler's theorem.)

Problem 7. How many ordered pairs $(a, b)$ of positive integers satisfy $\text{lcm}(a, b) = n$?

For $n = p_1^{e_1} \cdots p_k^{e_k}$: each prime $p_i$ contributes independently. If $a$ has $p_i^{\alpha_i}$ and $b$ has $p_i^{\beta_i}$, then $\max(\alpha_i, \beta_i) = e_i$.

Pairs $(\alpha_i, \beta_i)$ with $\max = e_i$: total pairs with both $\leq e_i$ is $(e_i+1)^2$; subtract pairs where both $\leq e_i - 1$, giving $(e_i+1)^2 - e_i^2 = 2e_i + 1$.

Total ordered pairs: $\prod_{i=1}^k (2e_i + 1) = \tau(n^2)$.

---

The pattern connecting everything

$\tau(n) = \sum_{d \mid n} 1 \qquad \sigma(n) = \sum_{d \mid n} d \qquad \sigma_k(n) = \sum_{d \mid n} d^k$

These are all special cases of Dirichlet series — sums over divisors. The deeper theory of how they multiply and interact is the Dirichlet convolution, which lives in Dirichlet's Divisor Problem.