3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Independence of variables implies multiplications, so multiply all $k_i + 1$ to get all permutations. I had overlooked to consider the $1$. $\endgroup$ – Giogre Nov 26 '20 at 8:31
  • 1
    $\begingroup$ Yes, exactly. If we pick $p_i^0$, we basically picking $1$ as a factor as you said. That's also possible. $\endgroup$ – ArsenBerk Nov 26 '20 at 8:35
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I see, quite straightforward, my question is standard theory then. $\endgroup$ – Giogre Nov 26 '20 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.