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?

  • 3
    $\begingroup$ Related question with my answer $\endgroup$ – George V. Williams Jul 1 '13 at 18:13
  • $\begingroup$ We are making a (positive) factor $m$ of $n$, where $n$ has the prime power factorization $n=p_1^{a_1}\cdots p_k^{a_k}$. Imagine $k$ bins, where Bin 1 has $a_1$ $p_1$'s and so on. We stop in front of Bin 1, decide how many $p_1$'s to "give" to $m$, $0$ to $a_1$, so $a_1+1$ choices. For every such choice, there are $a_2+1$ ways to decide how many $p_2$'s from Bin 2 to give to $m$. And so on. $\endgroup$ – André Nicolas Jul 1 '13 at 18:21

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.


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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.