扩展：整数因子之和

The sum of factors of a positive integer is an arithmetic function, denoted by $\sigma(n)$. For example, $\sigma(1)=1$ and $\sigma(6)=6+3+2+1=12$.

How could we derive a formula for $\sigma(n)$?

It is good advice to look at simpler cases until we fully understand what we're dealing with. Let's follow this method.

The divisors of a number have more to do with their prime factorization than with their size, so the latter two ideas could help us understand $\sigma$ more swiftly, however you still may be able to gain some insight by trying to devise a nifty method to add the divisors of, say, $720$. But enough chatter, let's start exploring!

If $n=p$ is prime, of course $\sigma(p)=p+1$, nothing to do here.

If $n=pq$ where $p,q$ are primes, then $\sigma(pq)=pq+p+q+1=(p+1)(q+1)$. Wow, nice factorization!

What about $n=p^2q$? Then

$$\sigma(p^2q)=1+q+p+pq+p^2+p^2q$$ $$=(1+q)+p(1+q)+p^2(1+q)=(1+p+p^2)(1+q).$$

Aha!

Let the prime factorization of $n$ be $n=p_1^{k_1}p_2^{k_2}...p_r^{k_r}$. Its divisors are all the numbers of the form $p_1^{\ell_1}p_2^{\ell_2}...p_r^{\ell_r}$, where $0\le \ell_i\le k_i$ for each $i$. These are the numbers we want to add up.

The beautiful observation is that the following product, when expanded, generates each divisor of $n$ exactly once:

$$(1+p_1+...+p_1^{k_1})\cdot (1+p_2+...+p_2^{k_2})\cdot \ldots\cdot (1+p_r+...+p_r^{k_r}).$$

Indeed, $p_1^{\ell_1}p_2^{\ell_2}...p_r^{\ell_r}$ is obtained exactly once: when we choose $p_i^{\ell_i}$ from the $i$-th bracket.

It remains to polish this formula a bit. To this end, we apply the formula for the geometric series to get

$$\sigma(n)=\frac{{p_1}^{k_1+1}-1}{p_1-1}\cdot \ldots\cdot \frac{{p_r}^{k_r+1}-1}{p_r-1}.$$

Or, with product notation,

$$\sigma(n)=\prod_{i=1}^r \frac{{p_i}^{k_i+1}-1}{p_i-1}.$$

From this it follows that $\sigma$ is multiplicative as well.

One may even generalize to the sum of the $k$-th powers of the divisors of a positive integer $n$, denoted by $\sigma_k(n)$. You may try your hand at proving a formula for it in the practice problems.

Finding the sum of the factors of a positive integer is a very useful an interesting endeavor. Similar to other problems involving factors, it is often possible to find the answer using "brute force" for small numbers. For example, the sum of the factors of $14$ is found by first identifying the factors of $14$ as $1, 2, 7,$and $14$. Adding these together we get $1+2+7+14=24$.

Just like finding the number of factors and finding the product of factors is simple for small numbers using this method, but very tedious for large numbers, finding the sum of factors is also simple for small numbers and very tedious for large numbers using this method.

Do you know the algorithm for find the number of factors of an integer?

As a quick refresher, lets look at the example of $18$. The number of factors is $6$ as you probably determined when you answered the problem above. The algorithm first calculates the prime factorization of $18=2\cdot3^2$. Then you add $1$ to each of the exponents (remembering $2 = 2^1$) and find the product $(1+1)(2+1)=2\cdot3=6$. The reason this works is because it recognizes that every factor $18$ can be written in the form $2^a\cdot3^b$ where $a$ is either $0$ or $1$ and $b$ is $0, 1,$ or $2$. Those factors are listed below: $$1=2^0\cdot3^0$$ $$2=2^1\cdot3^0$$ $$3=2^0\cdot3^1$$ $$6=2^1\cdot3^1$$ $$9=2^0\cdot3^2$$ $$18=2^1\cdot3^2$$ The key to finding the sum of the factors is embedded in this list of factors and how they are derived. Perform the following polynomial multiplication and while you are working the problem, consider how this might apply to the problem at hand.

Do you see it? If not, replace $a$ with $2$ and $b$ with $3$ and then turn the subscripts into exponents. So $$(2^0+2^1)(3^0+3^1+3^2)=2^0\cdot3^0+2^1\cdot3^0+2^0\cdot3^1+2^1\cdot3^1+2^0\cdot3^2+2^1\cdot3^2$$ $$=1+2+3+6+9+18$$ Which is exactly the sum of the 6 factors. However, if I asked you to find $(2^0+2^1)(3^0+3^1+3^2)$ you wouldn't use the distributive property. Instead you would replace $(2^0+2^1)$ with $3$ and $(3^0+3^1+3^2)$ with $13$ so: $$(2^0+2^1)(3^0+3^1+3^2)=3\cdot13=39$$ Thus we have our algorithm. The sum of the factors of any number is simply the product of the sums of the powers of each prime factor from $0$ to the exponent in the prime factorization. For example, the prime factorization of $600=2^3\cdot3\cdot5^2$. From this we find the sum of the factors by using the algorithm as shown below: $$(2^0+2^1+2^2+2^3)(3^0+3^1)(5^0+5^1+5^2)=$$ $$(1+2+4+8)(1+3)(1+5+25)=$$ $$15\cdot4\cdot31=1860$$ Try one on your own:

A perfect number is a positive integer $n$ satisfying the equation $\sigma(n)=2n$. For example, $6$ is a perfect number because $1+2+3=6$, or $28$ is a perfect number because $1+2+4+7+14=28$.

Prove that an even positive integer is a perfect number if and only if it can be written in the form $2^{p-1}(2^p-1)$, where $p$ and $2^p-1$ are prime numbers.

Note:

The "if" part is quite simple, but the "only if" part is a harder result due to Euler. However, the proof only employs simple facts, which you probably already know.

It is well-known and easy to prove that if $2^p-1$ is a prime number, then $p$ is prime. Such primes are known as Mersenne primes.

Using the formulas for $\sigma$ and $\varphi$ (see here), prove that

$$\varphi(n)\sigma(n)\le n^2$$

for every positive integer $n$.

Prove the formula

$$\sigma_k(n)=\prod_{i=1}^r \frac{{p_i}^{k(\alpha_i+1)}-1}{{p_i}^k-1},$$

where $k$ is a positive integer (actually, it may be any nonzero real number), and $n$ has prime factorization $n=p_1^{\alpha_1}p_2^{\alpha_2}... p_r^{\alpha_r}$.

Compare this with the result for the divisor function.