Unipal Initiative - Free Competition Math Courses, From Students For Students

Both divisor functions below are multiplicative: if $\gcd(a,b)=1$ , then $f(ab)=f(a)f(b)$ . That property is what lets you compute them prime-power by prime-power and multiply the results, rather than examining every divisor individually.

Number of divisors, $\tau(n)$

For $n=p_1^{e_1}\cdots p_k^{e_k}$ :

\tau(n) = (e_1+1)(e_2+1)\cdots(e_k+1)

Sum of divisors, $\sigma(n)$

Each prime’s contribution is a geometric series, summed over its powers from 0 to $e_i$ :

\sigma(n) = \prod_{i} \left(1+p_i+p_i^2+\cdots+p_i^{e_i}\right) = \prod_i \dfrac{p_i^{e_i+1}-1}{p_i-1}

Worked example

Problem: Find $\tau(360)$ and $\sigma(360)$ , given $360=2^3\cdot3^2\cdot5$ .

Solution:

\tau(360) = (3+1)(2+1)(1+1) = 4\times3\times2=24

\sigma(360) = (1+2+4+8)(1+3+9)(1+5) = 15\times13\times6 = 1170

Practice problems

1.Find $\tau(100)$ , given $100=2^2\times5^2$ .

2.Find $\sigma(28)$ , given $28=2^2\times7$ , and check whether 28 is a “perfect number” ( $\sigma(n)=2n$ ).

3.Find the smallest $n$ with exactly 6 divisors.

4.Find $\sigma(45)$ , given $45=3^2\times5$ .

Divisor Functions

Number of divisors, τ(n)\tau(n)τ(n)

Sum of divisors, σ(n)\sigma(n)σ(n)

Practice problems

Number of divisors, $\tau(n)$

Sum of divisors, $\sigma(n)$