Counting Divisors Proof

Question

How can be proved that the number of positive divisors is equal to:$$ (e_{1}+1)(e_{2}+1)....(e_{n}+1) \ $$

where $e_{i}$ is the ith exponent of the prime factorization.

Answer 1

HINT: If $m=\prod_{k=1}^np_k^{e_k}$, the divisors of $m$ are precisely the numbers of the form $\prod_{k=1}^np_k^{d_k}$, where $d_k\in\{0,1,\ldots,e_k\}$ for $k=1,\ldots,n$. (Why?) Thus, each divisor of $m$ corresponds to a unique $n$-tuple $\langle d_1,\ldots,d_n\rangle$ of this type. How many such $n$-tuples are there?

Answer 2

Idea of proof:

Let $p_0,\ldots, p_i$ be the $i$ prime factors of $n$. That is: $$n = p_0^{e_0}p_1^{e_1}\cdots p_i^{e_i}$$

Then, the number of unique positive divisors is the same as the number of ways to select unique combinations of the $e_k$s.

There are $e_0+1$ ways to select exponent for $p_0$, $e_1+1$ ways to select the exponent for $p_1$, etc. The result follows immediately.

Answer 3

Let $d(n)$ denote the number of divisors of $n$. Now prove the following:

1. If $\gcd(m,n)=1$, then $d(mn) = d(m) \cdot d(n)$. This is because any divisor of $mn$ can be uniquely written as the product of a divisor of $m$ times a divisor of $n$. Conversely, any product of divisor of $m$ and divisor of $n$ is a divisor of $mn$.
2. If $p$ is a prime, then $d(p^a) = a+1$; the only divisors being $1, p, p^2, \cdots, p^a$.

Combine these two and use induction to obtain what you want.

Answer 4

By the Fundamental Theorem of Arithmetic, you can write $$ N = p_1^{e_1} p_2^{e_2} \cdots p_n^{e_n}, $$ where the primes and their exponents are uniquely determined by the number $N$. Any factor of $k$ of $N$ must also be written $$ k = p_1^{d_1} p_2^{d_2} \cdots p_n^{d_n}, $$ where the exponents are no greater: $$ \left\{ \begin{align} 0 \le & d_1 \le e_1 \\ 0 \le & d_2 \le e_2 \\ & \vdots \\ 0 \le & d_n \le e_n \end{align} \right. $$

There are $e_1 +1$ integers $d_1$ satisfying the first inequality, $e_2 + 1$ integers $d_2$ satisfying the second, etc. So, the number of possible lists of exponents $(d_1, d_2, \ldots, d_n)$ is $$ (e_1 + 1)(e_2 + 1) \cdots (e_n + 1). $$