# Number of proper divisors generally prime

If we count the number of proper divisors of a positive integer, why do we usually get a prime number (or $1$)?

n   # Proper divisors of n
--------------------------
2   1
3   1
4   2
5   1
6   3
7   1
8   3
9   2
10  3
11  1
12  5
13  1
14  3
15  3
16  4 <
17  1
18  5
19  1
20  5


Note that $16$ does not follow the rule, which initially led me to believe that certain square numbers were exceptions. This is true (e.g. prime numbers squared, which have two proper divisors), but something funky happens around square numbers that I do not understand.

For instance, $49$ follows the rule, but $48$ does not. Both $81$ and $80$ do not follow the rule. $121$ follows the rule but $120$ does not. Then there seem to be some random numbers that do not follow the rule as well, such as $162$.

Is there any pattern here? Am I missing something obvious?

-
Does this actually hold generally? Writing $$n=p_1^{k_1}\cdots p_m^{k_m},$$ where $p_1<\cdots<p_m$ are primes and the $k_j$ are positive integers, the number of proper factors of $n$ is $$(k_1+1)\cdots(k_m+1)-1.$$ I see no reason to suspect that this will "usually" be prime, especially for larger $n$. – Cameron Buie Apr 6 '13 at 21:08

## 2 Answers

If the prime factorization of $N$ is $\prod_i p_i^{\alpha_i}$ where the $p_i$s are all different, then the total number of divisors is $\prod_i (\alpha_i+1)$, and the number of proper divisors is 1 less than that.

So it is trivial to manufacture a number with any desired number of proper divisors -- nothing forces it to be prime.

The hardest number of proper divisors to reach is seen to be ones that are a prime minus one; they can only be reached by having the original number be a prime power.

It is dangerous to try to conclude anything from a table that goes op to 20 only; unusually many among these first numbers are prime, and you're not going far enough to reach a high power of anything.

-

All you need is to analyze the formula for the number of divisors. If $n = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}$, we then have the number of divisors as $$d(n) = (1+\alpha_1)(1+\alpha_2)\cdots (1+\alpha_k)$$ The number of proper divisors is $$(1+\alpha_1)(1+\alpha_2)\cdots (1+\alpha_k) - 1$$

If $n$ is square, then $\alpha_j$'s are even. Hence, we have $(1+\alpha_1)(1+\alpha_2)\cdots (1+\alpha_k)$ to be odd and hence $$(1+\alpha_1)(1+\alpha_2)\cdots (1+\alpha_k) - 1$$ is even. Hence, if $n$ is a square the number of proper divisors is even. If $n$ is a square and is not of the form $p^2$, where $p$ is a prime, then the number of proper divisors is an even number greater than $2$ and hence is always composite.

However, this doesn't mean that if the number of proper divisors is composite, the number has to be a square. All this means is if the number of proper divisors is even, then the number has to be a square.

-