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)$$

  • $\begingroup$ 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$. $\endgroup$ Sep 5 '16 at 15:17
  • $\begingroup$ You can demonstrate it using induction, first on $a$ with $k=1$ and then on $k$ $\endgroup$
    – Henry
    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)$


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.