4

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

learning
  • 1,749
  • 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$. – barak manos Sep 05 '16 at 15:17
  • You can demonstrate it using induction, first on $a$ with $k=1$ and then on $k$ – Henry Sep 05 '16 at 15:17

2 Answers2

3

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

GoodDeeds
  • 11,185
  • 3
  • 22
  • 42
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)$

SchrodingersCat
  • 24,472