Number TheoryDifficulty 20-80173 tagged problems

Divisor Functions

Divisor Functions is the habit of reading the count and sum of divisors off the prime factorization. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$\text{For } n = \prod_i p_i^{e_i}: \quad \tau(n) = \prod_i (e_i + 1), \qquad \sigma(n) = \prod_i \frac{p_i^{e_i+1} - 1}{p_i - 1}$$

Once you know the prime factorization, the count of divisors $\tau(n)$ and the sum of divisors $\sigma(n)$ both read off directly as products over the prime powers.

Why It Works

1
Every divisor of $n = \prod_i p_i^{e_i}$ has the form $\prod_i p_i^{f_i}$ with $0 \le f_i \le e_i$, choosing each exponent independently.
2
Prime $p_i$ offers $e_i + 1$ choices for $f_i$, so multiplying the choices gives the divisor count $\tau(n) = \prod_i (e_i + 1)$.
3
The sum of all divisors factors the same way: $\sigma(n) = \prod_i \left(1 + p_i + p_i^2 + \cdots + p_i^{e_i}\right)$, since expanding the product hits every divisor exactly once.
4
Each factor is a finite geometric series summing to $\frac{p_i^{e_i+1} - 1}{p_i - 1}$, giving the closed form for $\sigma(n)$. Both $\tau$ and $\sigma$ are multiplicative: $\tau(mn) = \tau(m)\tau(n)$ and $\sigma(mn) = \sigma(m)\sigma(n)$ when $\gcd(m,n) = 1$.

Worked Examples

Example 1

Find the number of divisors $\tau(72)$ and the sum of divisors $\sigma(72)$.

1
Factor: $72 = 8 \cdot 9 = 2^3 \cdot 3^2$.
2
Count divisors: $\tau(72) = (3 + 1)(2 + 1) = 4 \cdot 3 = 12$.
3
Sum divisors via the geometric-series factors: $\sigma(72) = \frac{2^{4} - 1}{2 - 1} \cdot \frac{3^{3} - 1}{3 - 1} = \frac{15}{1} \cdot \frac{26}{2} = 15 \cdot 13$.
4
Multiply: $15 \cdot 13 = 195$. (Check: $1+2+3+4+6+8+9+12+18+24+36+72 = 195$.)

Answer:

$\tau(72) = 12$, $\sigma(72) = 195$

Warm-up

For how many integers $n$ with $1 \le n \le 100$ is $\tau(n)$ odd?

1
Write $n = \prod p_i^{e_i}$, so $\tau(n) = \prod (e_i + 1)$. This product is odd iff every factor $e_i + 1$ is odd, i.e. every exponent $e_i$ is even.
2
All exponents even means $n$ is a perfect square. So $\tau(n)$ is odd exactly when $n$ is a perfect square.
3
Count perfect squares in $[1, 100]$: $1^2, 2^2, \dots, 10^2$.
4
That is $10$ values.

Answer:

$10$

Contest level

Find the sum of the divisors of $n = 2^4 \cdot 3^2$ that are themselves perfect squares.

1
A divisor has the form $2^a 3^b$ with $0 \le a \le 4$ and $0 \le b \le 2$. It is a perfect square iff both $a$ and $b$ are even.
2
Allowed exponents: $a \in \{0, 2, 4\}$ and $b \in \{0, 2\}$.
3
The sum factors just like $\sigma$ over independent prime choices: $(2^0 + 2^2 + 2^4)(3^0 + 3^2) = (1 + 4 + 16)(1 + 9)$.
4
Compute: $21 \cdot 10 = 210$.

Answer:

$210$

Olympiad / Challenge

Prove that the product of all positive divisors of $n$ equals $n^{\tau(n)/2}$.

1
Let $P = \prod_{d \mid n} d$. Pair each divisor $d$ with its complement $n/d$, which is also a divisor; as $d$ ranges over all divisors, so does $n/d$.
2
Multiply the two listings: $P \cdot P = \prod_{d \mid n} d \cdot \prod_{d \mid n} \frac{n}{d} = \prod_{d \mid n}\left(d \cdot \frac{n}{d}\right) = \prod_{d \mid n} n = n^{\tau(n)}$.
3
Therefore $P^2 = n^{\tau(n)}$, so $P = n^{\tau(n)/2}$ (taking the positive root, valid since $P > 0$).
4
The exponent $\tau(n)/2$ is an integer when $\tau(n)$ is even; when $\tau(n)$ is odd ($n$ a perfect square), the unpaired middle divisor is $\sqrt n$, and $n^{\tau(n)/2} = (\sqrt n)^{\tau(n)}$ is still an integer, so the formula holds in all cases. (Check $n = 12$: divisors $1,2,3,4,6,12$ multiply to $1728 = 12^3 = 12^{6/2}$. ✓)

Answer:

$\prod_{d \mid n} d = n^{\tau(n)/2}$.

Going Deeper

Generalization: $\tau = \sigma_0$ and $\sigma = \sigma_1$ are the special cases $k = 0, 1$ of $\sigma_k(n) = \sum_{d \mid n} d^k = \prod_i \frac{p_i^{k(e_i+1)} - 1}{p_i^k - 1}$. All $\sigma_k$ are multiplicative, as are $\varphi$, the Möbius function $\mu$, and any Dirichlet convolution of multiplicative functions — the unifying structure behind these formulas.
Where it appears: divisor-counting and divisor-sum problems, perfect/abundant/deficient number questions ($\sigma(n)$ vs $2n$), 'smallest $n$ with exactly $D$ divisors', and parity tricks ($\tau(n)$ odd iff $n$ is a perfect square, since divisors pair up except a square root).
Pitfall: $\tau$ and $\sigma$ are multiplicative only across COPRIME factors — $\tau(mn) = \tau(m)\tau(n)$ holds if and only if $\gcd(m,n) = 1$. For example $\tau(4 \cdot 3) = \tau(4)\tau(3) = 3 \cdot 2 = 6$ because $\gcd(4,3) = 1$, but $\tau(2 \cdot 6) \neq \tau(2)\tau(6)$ since $\gcd(2,6) = 2$ (indeed $\tau(12) = 6$ while $\tau(2)\tau(6) = 2 \cdot 4 = 8$). Always split into coprime (prime-power) pieces before multiplying, and remember $\sigma(n)$ counts $1$ and $n$ among the divisors.

Spot the Signal

Use it when a problem asks how many divisors a number has, or for their sum.
You can describe the hard part as reading the count and sum of divisors off the prime factorization, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by writing $n = \prod p_i^{e_i}$ and applying $\tau = \prod (e_i + 1)$ or the $\sigma$ product formula.
Name the relation that makes Divisor Functions legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Forgetting the $+1$ on each exponent, or treating a composite as prime.
Applying Divisor Functions because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Factor first; the exponents alone tell you how many divisors there are.

Try it on:

Count or sum the divisors of a number in a contest problem.