Divisor Functions

Definition. The sum of divisors function is given by

$$\sigma(n) = \sum_{d \mid n} d.$$

The number of divisors function is given by

$$\tau(n) = \sum_{d \mid n} 1.$$


Example. Recall that a number is perfect if it's equal to the sum of its divisors other than itself. It follows that a number n is perfect if $\sigma(n) = 2n$ .


Example.

$$\sigma(15) = 1 + 3 + 5 + 15 = 24 \quad\hbox{and}\quad \tau(15) = 4.\quad\halmos$$


I want to show that $\sigma$ and $\tau$ are multiplicative. I can do most of the work in the following lemma.

Lemma. The divisor sum of a multiplicative function is multiplicative.

Proof. Suppose f is multiplicative, and let $D(f)$ be the divisor sum of f. Suppose $(m,n) = 1$ . Then

$$[D(f)](m) = \sum_{a \mid m} f(a) \quad\hbox{and}\quad [D(f)](n) = \sum_{b \mid n} f(b).$$

Then

$$[D(f)](m)\cdot [D(f)](n) = \left(\sum_{a \mid m} f(a)\right) \left(\sum_{b \mid n} f(b)\right) = \sum_{a \mid m} \sum_{b \mid n} f(a)f(b).$$

Now $(m,n) = 1$ , so if $a \mid m$ and $b \mid n$ , then $(a,b)
   = 1$ . Therefore, multiplicativity of f implies

$$[D(f)](m)\cdot [D(f)](n) = \sum_{a \mid m} \sum_{b \mid n} f(ab).$$

Now every divisor d of $mn$ can be written as $d = ab$ , where $a
   \mid m$ and $b \mid n$ . Going the other way, if $a \mid m$ and $b \mid
   n$ then $ab \mid mn$ . So I may set $d = ab$ , where $d \mid mn$ , and replace the double sum with a single sum:

$$[D(f)](m)\cdot [D(f)](n) = \sum_{d \mid mn} f(ab) = [D(f)](mn).$$

This proves that $D(f)$ is multiplicative.


Example. The identity function $\id(x) = x$ is multiplicative: $\id(mn) = mn = \id(m)\cdot \id(n)$ for all m, n (so a fortiori for $(m,n) = 1$ ). Therefore, the divisor sum of $\id$ is multiplicative. But

$$[D(\id)](n) = \sum_{d \mid n} \id(d) = \sum_{d \mid n} d = \sigma(n).$$

Hence, the sum of divisors function $\sigma$ is multiplicative.


Example. The constant function $I(n) = 1$ is multiplicative: $I(mn) = mn = I(m)\cdot I(n)$ for all m, n (so a fortiori for $(m,n) = 1$ ). Therefore, the divisor sum of I is multiplicative. But

$$[D(I)](n) = \sum_{d \mid n} I(d) = \sum_{d \mid n} 1 = \tau(n).$$

Hence, the number of divisors function $\tau$ is multiplicative.


I'll use multiplicativity to obtain formulas for $\sigma(n)$ and $\tau(n)$ in terms of their prime factorizations (as I did with $\phi$ ). First, I'll get the formulas in the case where n is a power of a prime.

Lemma. Let p be prime. Then:

$$\sigma(p^k) = \dfrac{p^{k+1} - 1}{p - 1}$$

$$\tau(p^k) = k + 1$$

Proof. The divisors of $p^k$ are 1, p, $p^2$ , ..., $p^k$ . So the sum of the divisors is

$$\sigma(p^k) = 1 + p + p^2 + \cdots + p^k = \dfrac{p^{k+1} - 1}{p - 1}.$$

And since the divisors of $p^k$ are 1, p, $p^2$ , ..., $p^k$ , there are $k + 1$ of them, and

$$\tau(p^k) = k + 1.\quad\halmos$$

Theorem. Let $n = p_1^{r_1}\cdots p_k^{r_k}$ , where the p's are distinct primes and $r_i \ge 1$ for all i. Then:

$$\sigma(n) = \left(\dfrac{p_1^{r_1+1} - 1}{p_1 - 1}\right)\cdots \left(\dfrac{p_k^{r_k+1} - 1}{p_k - 1}\right)$$

$$\tau(n) = (r_1 + 1)\cdots (r_k + 1)$$

Proof. These results follow from the preceding lemma, the fact that $\sigma$ and $\tau$ are multiplicative, and the fact that the prime power factors $p_i^{r_i}$ are pairwise relatively prime.

Here is a graph of $\sigma(n)$ for $1 \le n \le 1000$ .

$$\hbox{\epsfysize=2in \epsffile{divisor-functions1.eps}}$$

Note that if p is prime, $\sigma{p} = p + 1$ . This gives the point $(p, p + 1)$ , which lies on the line $y = x + 1$ . This is the line that you see bounding the dots below.

Here is a graph of $\tau(n)$ for $1 \le n \le 1000$ .

$$\hbox{\epsfysize=2in \epsffile{divisor-functions2.eps}}$$

If p is prime, $\tau(p) = 2$ . Thus, $\tau$ repeatedly returns to the horizontal line $y = 2$ , which you can see bounding the dots below.


Example. $720 = 2^4\cdot 3^2\cdot 5$ , so

$$\sigma(720) = \left(\dfrac{2^5 - 1}{2 - 1}\right) \left(\dfrac{3^3 - 1}{3 - 1}\right) \left(\dfrac{5^2 - 1}{5 - 1}\right) = 2418,$$

$$\tau(720) = (4 + 1)(2 + 1)(1 + 1) = 30.\quad\halmos$$


Example. For each n, there are only finitely many numbers k whose divisors sum to n: $\sigma(k) = n$ . For k divides itself, so

$$n = \sigma(k) = (\hbox{junk}) + k > k.$$

This says that k must be less than n. So if I'm looking for numbers whose divisors sum to n, I only need to look at numbers less than n. For example, if I want to find all numbers whose divisors sum to 42, I only need to look at $\{1,
   2, \ldots, 41\}$ .


Contact information

Bruce Ikenaga's Home Page

Copyright 2008 by Bruce Ikenaga