Arithmetics: Number of divisors of an positive integer, their sum and product

Question

So I've just started studying arithmetics a month ago, and I've came across this problem. Let's say $$ k = \prod_{m = 1}^n p_m^{i_m} \in \mathbb{N} $$ and let $d(k)$ denote the number of $k$'s divisors, $\pi(k)$ be the product of these divisors and $S(k)$ their sum.

I need to prove that $$d(k)=\prod_{m=1}^n \left(i_m+1\right),$$ which is intuitively true but I don't know how to express it on paper.

And I also need to find the expressions for $S(k)$ and $\pi(k)$. Thank you.

Answer 1

Assuming that in your prime factorization, the primes $p_i$ are distinct, then any divisor $d$ of $k$,$d$ may contain only(maybe not all) the primes $p_i$ in its prime factorization, and furthermore, if $d = \prod_{m=1}^n p_m^{j_m}$,then we must have $0 \leq j_m \leq i_m$ for all $m$.

On the other hand, if we actually choose $0 \leq l_m \leq i_m$, $1 \leq m \leq n$, and form the number $f=\prod_{m=1}^n p_m^{l_m}$, then clearly, $f$ is a divisor of $k$.

So, every divisor of $k$, is given by a unique choice of $0 \leq j_m \leq i_m$ for all $1 \leq m \leq n$, since we can form the number $\prod_{m=1}^n p_m^{j_m}$.

Hence, the answer is the number of choices we can make, which is just $\prod_{m=1}^n (i_m + 1)$, since for each $m$ we have $i_m+1$ choices for $j_m$, and they can be chosen independently of other $m$.

For the other questions, well, the product is not so difficult.

Let $k$ not be a perfect square. Then, there is no divisor $d$ such that $d^2 = k$. Pair up every divisor $d$, with $\frac kd$, which is another divisor.

That is, $$ \pi(k) = \prod_{d | k} d = \prod_{d | k , d< \sqrt k} d \times \frac kd = k^{|S|} $$ where $S$ is the number of divisors of $k$, which are below $\sqrt k$. But then, this is exactly half the number of divisors of $k$, because again, it is possible to pair up divisors of $k$ above and below $\sqrt k$ as we did earlier.

So, we get $|S| = \frac {d(k)}2 \implies \pi(k) = k^{\frac {d(k)}2}$.

For example, $k=8 \implies 1 \times 2\times 4\times 8 = 64$, and $d(k) = 4$, so $8^{(\frac 42)} = 8^2 = 64$ as well.

If $k$ is a perfect square, then again there are pairs like last time. However, there is also a divisor, namely $\sqrt k$, which doesn't quite pair up with anything, and so sticks out. Following the previous logic, we get $\pi(k) = \sqrt k \times k^{|S|}$, where $S$ is defined as before, but then this time, $|S| = \frac{d(k) \color{red}{-1}}{2}$ because we cannot pair up the divisor $\sqrt k$ with anything else.

Therefore, $\pi(k) = k^{\frac 12} \times k^{\frac{d(k) - 1}{2}} = k^{\frac {d(k)}2}$, again! (note that $\frac{d(k)}{2}$ is a half integer, but $k$ is a perfect square, so it compensates).

For example, $k = 9$, then $1,3,9$ are the divisors, and the product is $27$, which is $9^{(\frac 32)}$.

The sum $S_k$ is a very cute observation : consider the following product: $$ (1 + p_1 + p_1^2 + ... + p_1^{i_1}) (1 + p_2 + p_2^2 + ... + p_2^{i_2}) ... (1 + p_n + p_n^2 + ... + p_n^{i_n}) $$ Let $d = \prod p_m^{j_m}$ be any factor of $k$. Then, $d$ occurs in the above summation, because you can take the terms $p_i^{j_i}$ from each individual summation, and their product is $d$.

However, every such $d$ appears precisely once, by unique prime factorization. That is, the above expression is the sum of the divisors of $d$.

A small use of the geometric formula gives: $$ \bbox[yellow] {S(k) = \prod_{m=1}^n \frac{p_m^{i_m + 1} - 1}{p_m - 1}} $$

For example, the sum of divisors of $6$ is $(1+2)(1+3) = 12$, which is true since $1 + 2 + 3 + 6 = 12$.

Answer 2

To get the formula for $d(k)$, look at $k = \prod_{m = 1}^n p_m^{i_m} \in \mathbb{N}$.

The $m$-th exponent can take $i_m+1$ values, from $0$ to $i_m$.

Therefore, since these can be chosen independently for each $m$, the total number of choices is the product of these.

You can also prove the formula by induction on $n$.

Answer 3

To construct a divisor of $k$, one needs to pick which powers of the corresponding prime factors should participate. To do that, for each prime $p_m$, you can use any power from $0$ to $i_m$, which gives a total of $(i_m+1)$ choices.

Since all choices are independent, you end up with $d(k)$ as the product of individual factors.

Now consider the product of the divisors. Can you compute how many times will each $p_m$ be included in the final result?

For the sums, writing out the expression for a couple of small examples, e.g. $18 = 2^1 \cdot 3^2$ will quickly show you how to sum it using a geometric series.