Prime factors + number of Divisors

I know that one way to find the number of divisors is to find the prime factors of that number and add one to all of the powers and then multiply them together so for example

$$555 = 3^1 \cdot 5^1 \cdot 37^1$$

therefore the number of divisors = $(1+1)(1+1)(1+1) = 2 \cdot 2 \cdot 2 = 8$

What I do not know (and can't seem to find when I look) is WHY this relationship exists or a formula which shows its proof.

Has anyone seen such a formula?

Solution 1:

If you write $n= \prod\limits_{i=1}^n {p_i}^{e_i}$, then the number of divisors of $n$ is the number of different products you can make of the form $\prod\limits_{i=1}^n {p_i}^{f_i}$ where $f_i \leq e_i$. For each prime, there are $e_i+1$ choices for $f_i$ and so the total number of choices is $\prod\limits_{i=1}^n (e_i+1)$ as you suggest.

Solution 2:

Let $d(n)$ be the number of divisors for the natural number, $n$.

We begin by writing the number as a product of prime factors: $n = p^aq^br^c...$ then the number of divisors, $d(n) = (a+1)(b+1)(c+1)...$

To prove this, we first consider numbers of the form, $n = p^a$. The divisors are $1, p, p^2, ..., p^a$; that is, $d(p^a)=a+1$.

Now consider $n = p^aq^b$. The divisors would be:

$1, p, p^2, ..., p^a,$

$q, pq, p^2q, ..., p^aq,$

$q^2, pq^2, p^2q^2, ..., p^aq^2,$

$..., ..., ..., ..., ...,$

$q^b, pq^b, p^2q^b, ..., p^aq^b $

Hence we prove that the function, $d(n)$, is multiplicative, and in this particular case, $d(p^aq^b)=(a+1)(b+1)$. It should be clear how this can be extended for any natural number which is written as a product of prime factors.

http://mathschallenge.net/library/number/number_of_divisors