Toolkit 33

Number of Positive Divisors

n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}

\text{Number of positive divisors of }n:\;(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)

Proof

Suppose

n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k},

where $p_1, p_2, \ldots, p_k$ are distinct primes. Every positive divisor $d$ of $n$ has a unique form

d = p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k},

where

0\le\beta_1\le\alpha_1, \quad 0\le\beta_2\le\alpha_2, \quad\ldots,\quad 0\le\beta_k\le\alpha_k.

There are $\alpha_1+1$ possible choices for $\beta_1$ , namely $0, 1, \ldots, \alpha_1$ . Similarly, there are $\alpha_2+1$ choices for $\beta_2$ , and so on. Since these choices are independent, the total number of positive divisors of $n$ is

(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1). \quad\square

Back to Toolkit

Proof

Related Problems