2

I'm trying to prove that the number of divisors of any given number is $(a_1+1)(a_2+1)...(a_r+1)$ Where $a_1, a_2 ... a_r$ are from $p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$

The problem is that the proof seems too easy and hard to describe, I have a intuitive feeling that it is wrong. My argument for the proof is:

We can take any of the primes and raise it to any power between $0$ to $a_r$. That's $a_r+1$ combinations. I also know that in order to find the possible number of combinations for $X$ and $Y$ where $X$ can have any of $R$ values and $Y$ can have any of $T$ values is simply $RT$. Hence, the total number of combinations for the divisors comes out to be $(a_1+1)(a_2+1)...(a_r+1)$.

Aayush Agrawal
  • 1,207

2 Answers2

7

The idea is good, it just needs some polishing. First of all, the last formula should be $(a_1+1)(a_2+1)\dots(a_r+1)$ (I suppose it was a typo).

Let $d$ be a divisor of $n=p_1^{a_1}p_2^{a_2}\dots p_r^{a_r}$ (where $p_1,\dots,p_r$ are pairwise distinct prime numbers). Then $de=n$ for some $e$ and, by the fundamental theorem of aritmetic, $$ d=p_1^{b_1}p_2^{b_2}\dots p_r^{b_r} $$ for some $b_1,b_2,\dots,b_r$, with $0\le b_i\le a_i$. Conversely, any number of this form is a divisor. The fundamental theorem of arithmetic guarantees also that distinct choice of the $r$-tuple $(b_1,\dots,b_r)$ produces different divisors. Therefore the number of divisors is the same as the set of $r$-tuples $(b_1,\dots,b_r)$ with $$ 0\le b_i\le a_i,\qquad i=1,2,\dots,r $$ and these are in number of $(a_1+1)(a_2+1)\dots(a_r+1)$.

egreg
  • 238,574
1

Think of it in this way. Each one of the terms of the following product is a divisor of $d$

$$ (1+p_1+{p_1}^2+\cdots+{p_1}^{a_1})(1+{p_2}+{p_2}^2+\cdots+{p_2}^{a_2})\cdots(1+{p_r}+{p_r}^2+\cdots+{p_r}^{a_r}) $$

Hence number of divisors is the number of terms in this product which is basically

$$ (1+a_1)(1+a_2)\cdots(1+a_r) $$

dear chap
  • 116