Definition. The sum of divisors function is given by
The number of divisors function is given by
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 .
I want to show that and 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 be the divisor sum of f. Suppose . Then
Now , so if and , then . Therefore, multiplicativity of f implies
Now every divisor d of can be written as , where and . Going the other way, if and then . So I may set , where , and replace the double sum with a single sum:
This proves that is multiplicative.
Example. The identity function is multiplicative: for all m, n (so a fortiori for ). Therefore, the divisor sum of is multiplicative. But
Hence, the sum of divisors function is multiplicative.
Example. The constant function is multiplicative: for all m, n (so a fortiori for ). Therefore, the divisor sum of I is multiplicative. But
Hence, the number of divisors function is multiplicative.
I'll use multiplicativity to obtain formulas for and in terms of their prime factorizations (as I did with ). First, I'll get the formulas in the case where n is a power of a prime.
Lemma. Let p be prime. Then:
Proof. The divisors of are 1, p, , ..., . So the sum of the divisors is
And since the divisors of are 1, p, , ..., , there are of them, and
Theorem. Let , where the p's are distinct primes and for all i. Then:
Proof. These results follow from the preceding lemma, the fact that and are multiplicative, and the fact that the prime power factors are pairwise relatively prime.
Here is a graph of for .
Note that if p is prime, . This gives the point , which lies on the line . This is the line that you see bounding the dots below.
Here is a graph of for .
If p is prime, . Thus, repeatedly returns to the horizontal line , which you can see bounding the dots below.
Example. , so
Example. For each n, there are only finitely many numbers k whose divisors sum to n: . For k divides itself, so
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 .
Bruce Ikenaga's Home Page
Copyright 2008 by Bruce Ikenaga