Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
