# Prove the number of divisors

Can anyone help me to prove this? This is given as a fact, but I don't understand why it is true.

For an integer $n$ greater than 1, let the prime factorization of $n$ be $$n=p_1^ap_2^bp_3^cp_4^d...p_k^m$$ Where a, b, c, d, ... and m are nonegative integers, $p_1, p_2, ..., p_k$ are prime numbers. The number of divisors is $$d(n)=(a+1)(b+1)(c+1)....(m+1)$$

• HINT: $p_1$ can appear in any divisor of $n$ between $0$ and $a$ times. In other words, $p_1$ has $a+1$ different ways to "affect" a divisor of $n$. Sep 5 '16 at 15:17
• You can demonstrate it using induction, first on $a$ with $k=1$ and then on $k$ Sep 5 '16 at 15:17

This is solved using combinatorics. Any divisor $$x$$ of $$n$$ will be of the form $$x=p_1^{n_1}p_2^{n_2}\cdots p_k^{n_k}$$ where $$0\le n_1\le a$$, $$0\le n_2\le b$$, and so on.

The $$k$$-tuple $$(n_1,n_2,\cdots,n_k)$$ uniquely specifies a divisor. Thus, the number of divisors will be the number of ways of choosing $$n_1,n_2,\cdots,n_k$$ given the constraints.

The value of $$n_i$$ in $$x$$ is independent of the value of $$n_j$$ for all $$i\ne j$$. So, the number of ways of choosing $$x$$ will be the product of the number of ways of choosing $$n_i$$ for all $$1\le i\le k$$.

$$\text{Number of ways}=\Pi_i \text{ (Number of ways of choosing }n_i)$$

Now, $$n_1$$ can take any value from $$0$$ to $$a$$, $$n_2$$ from $$0$$ to $$b$$, and so on. That is, $$n_1$$ has $$(a+1)$$ choices, $$n_2$$ has $$(b+1)$$ choices, and so on.

Thus, $$\text{Number of ways}=(a+1)\times(b+1)\times\cdots\times(m+1)$$

Consider that all possible divisors of $n$ can be created by choosing from $p_1,p_2, \ldots, p_k$ in appropriate numbers.

So, for creating a particular divisor, we can choose $1$ $p_1$ or $2$ $p_1$'s or $3$ $p_1$'s and so on till a choice of all $a$ $p_1$'s. Then again we have the choice of not choosing any $p_1$ at all. So this amounts to $a+1$ choices.

Similarly for $p_2$, we have $b+1$ choices and in this way we can finally conclude that, for any $p_r$, $r=1,2,3 \ldots k$, we have $t'+1$ choices where $p_r$ is raised to the power $t'$ in the prime factorisation of $n$.

Finally since all $p_i$'s are distinct, we need to multiply the choices to get $d(n)$.

So total number of divisors possible $=d(n)=(a+1)(b+1)\ldots (m+1)$