Find the no. of ways in which a natural no. can be expressed as a product of two factors

combinatorics

The general formula for finding this is provided in this question (the same formula is given in my book, too, but without proof) which asked for a proof of the same. After reading the proof in the accepted answer, my brain is all factorised and broken up into pieces. Please help!

Please see my reasoning in the comments of @CambridgeGrad 's answer. Can you extend that reasoning to find the no. of ways in which a number can be expressed as a product of $n$ factors?

Best Answer

Let the unique prime factorisation of $N=p_1^{a_1}p_2^{a_2}\dotsm p_k^{a_k}$. The divisors of $N$ are precisely the numbers of the form, $$ d=p_1^{b_1}p_2^{b_2}\dotsm p_k^{b_k} $$ where $0\le b_i\le a_i$ for $1\le i\le k$. This gives $a_i+1$ choices for the exponent of $p_i$, and so $$c=(a_1+1)(a_2+1)\dotsm(a_k+1)$$ choices in total for divisors $d$. Your question resolves into how many ways you can form two factors out of $N$ such that their product is $N$. This is clearly of the form $N=d\cdot\frac{N}{d}$.

One thing to note is that $d=\frac{N}{d}$ if and only if $N=d^2$. Now if $N$ is not a perfect square the choices for $d$ run through $c$ choices, and also the number of choices for $\frac{N}{d}$ is also $c$; you can think of $N=d\cdot\frac{N}{d}$, and also $N=\frac{N}{d}\cdot d$ both occurring as we run through the $c$ choices for $d$ and $\frac{N}{d}$, so the number of distinct factorisations without regard to order is thus $\frac12 c$.

Now if $N$ is a perfect square, say $N=m^2$, we have that $m=\sqrt{N}$ is one divisor from our $c$ amount of choices, but gives rise to an extra product from the non-square case, this leads to two cases giving the same product, i.e., one where $\left(d,\frac{N}{d}\right)=(m,m)$ and one where $\left(\frac{N}{d},d\right)=(m,m)$, so this same product $m\cdot m$ gets counted twice and we thus have to half. Now we have a $c-1$ amount of the divisors distinct from $m$, and as before this leads to $\frac12 (c-1)$ amount of choices of these $c-1$ divisors as products. Now adding for the $m\cdot m$ product we have $\frac12 ((c-1)+2)=\frac12 (c+1)$ number if $N$ is a perfect square.

Related Question