# How to determine the number of divisors of an integer through combinatorics

How would you formally derive the fact that integer $$100$$ has 9 divisors $$(1,2,4,5,10,20,25,50,100)$$, knowing in advance that, apart from 1, its prime divisors are 2 and 5, each recurring 2 times $$(2 \cdot 2 \cdot\ 5 \cdot 5 = 100)$$?

This should be achievable using counting rules in combinatorics.

Yes, it is possible. Suppose we have $$n = p_1^{k_1}...p_m^{k_m}$$ where $$p_1,...,p_m$$ are distinct primes and $$k_1,...,k_m \ge 1$$. Then, for each prime factor $$p_i$$, we have the options $$\{0,1,...,k_i\}$$ for its power $$k_i$$ since $$p_i^a|p_i^{k_i}, \forall a \text{ such that } 0 \le a \le k_i$$. So we have $$k_i+1$$ options for each. Considering the fact that the prime factors are independent from other prime factors (as they are prime numbers), can you get a general result from here?
• Independence of variables implies multiplications, so multiply all $k_i + 1$ to get all permutations. I had overlooked to consider the $1$. Nov 26, 2020 at 8:31
• Yes, exactly. If we pick $p_i^0$, we basically picking $1$ as a factor as you said. That's also possible. Nov 26, 2020 at 8:35
The divisor counting function is usually noted with $$\tau(n)$$ (tau). In other words, $$n$$ has $$\tau(n)$$ divisors.
$$n=\prod_{i=1}^{m}p_m^{a_m}\Rightarrow\tau(n)=\prod_{i=1}^{m}(a_i+1)$$
The proof for this? Well observe that $$p^k$$ with prime $$p$$ has indeed $$k+1$$ divisors ($$1,p,...,p^k$$). Finally, observe that $$\tau\bigg(\prod_{i=1}^{m}p_m^{a_m}\bigg)=\prod_{i=1}^{m}\tau(p_i^{a_i})$$ and you are done.