A number theory problem by Andrea Palma

Sure, I'll do my best! If you have a prime factorisation of a number, then is VERY easy to say how many divisor the number has. For istance $8 = 2^3$ has $4$ divisors, namely $1,2,4,8$ . Note that the exponent of the factorisation in primes of $8$ is $3$ . You just have to increase this exponent by $1$ . $3+1 = 4$

This rule yelds for any power of prime. If $n = p^k$ , $p$ prime, then the number of divisors is $k+1$ . In fact the divisors of $n$ are $1=p^0, p=p^1, p^2, \ldots, p^k$ .

What happens when the number $n$ has a factorisation like $n= p^k q^h$ with $p,q$ distinct primes? We have these all these divisors $p^aq^b$ where $a \in \{0,1, \ldots, k\}$ and $b \in \{0,1, \ldots , h\}$ . So we have a divisor of $n$ for every couple $(a,b$ ) living in the cartesian product $\{ 0,1, \ldots, k\} \times \{0,1, \ldots , h\}$ that has $(k+1) (h+1)$ elements.

Now we can generalize this procedure. Let $n = p_1^{k_1}p_2^{k_2}\cdot \cdots \cdot p_t^{k_t}$ with $p_1, \ldots , p_t$ pairwise distinct primes. We have a divisor of $n$ everytime we have a number like $p_1^{a_1}p_2^{a_2}\cdot \cdots \cdot p_t^{a_t} n$ with $a_i \leq k_i$ .

So we have a different divisor (we are using the uniqueness of the prime factorisation) everytime we have a $t-$ -uple $(a_1, a_2, \ldots, a_t)$ living in the cartesian product

$\{0,1,\ldots , k_1\} \times \{0,1,\ldots , k_2 \} \times \cdots \times \{ 0,1,\ldots , k_t \}$

that has exactly $(k_1+1) \cdot (k_2 + 1) \cdot \cdots \cdot (k_t + 1$ ) elements. So the latter is also the number of divisors of $n$ .