# Find how many positive divisors a number has. What would you do?

Recently I learned an amazing thing. Suppose you are given a number and you have to find how many positive divisors it has. What would you do ?

Solution: Suppose you select $12$. It has $1,2,3,4,6,12$ as its divisors; so, total number of divisors of $12$ is $6$.

Now the method I learned:

$x={p_1}^a {p_2}^b$, where $p_1$ and $p_2$ are prime numbers. Now, $x$ has $(a+1)(b+1)$ positive divisors.

Note: Here $x$ can be expressed as a product of many primes with appropriate power.

I want to know the logic behind this.

• mathworld.wolfram.com/DivisorFunction.html Commented Jan 25, 2015 at 8:44
• Your $x$ must be the PRODUCT of $p_1^a$ and $p_2^b$. Please correct your typo, replace the plus sign. Commented Jan 25, 2015 at 9:04

This may give you more of the theory or logic that you want behind this (I give an explanation of your example specifically at the end), although Marco does provide a nice, intuitive combinatorial analysis.

As someone pointed out, $\sigma$ is the sum of divisors function, which is defined by setting $\sigma(n)$ equal to the sum of all the positive divisors of $n$.

Now, we have that $\tau$ is the number of divisors function, which is defined by setting $\tau(n)$ equal to the number of positive divisors of $n$.

First note that $\sigma(n)$ and $\tau(n)$ may be expressed in summation notation: $$\sigma(n)=\sum_{d\mid n}d\quad\text{and}\quad \tau(n)=\sum_{d\mid n}1.$$ I am going to assume that you know $\sigma(n)$ and $\tau(n)$ are multiplicative functions (if not, proofs of this fact are easy to find); that is, $$\sigma(mn)=\sigma(m)\sigma(n)\quad\text{and}\quad\tau(mn)=\tau(m)\tau(n),\tag{1}$$ where $m$ and $n$ are relatively prime positive integers (such functions are called completely multiplicative if $(1)$ holds for all positive integers $m$ and $n$).

With that out of the way, we can develop what you learned more rigorously by starting out with a lemma, then a theorem, and then a simple example.

Lemma: Let $p$ be prime and $a$ a positive integer. Then $$\sigma(p^a)=1+p+p^2+\cdots+p^a=\frac{p^{a+1}-1}{p-1},\tag{2}$$ and $$\tau(p^a)=a+1.\tag{3}$$ Proof. The divisors of $p^a$ are $1,p,p^2,\ldots,p^{a-1},p^a$. Hence, $p^a$ has exactly $a+1$ divisors, so that $\tau(p^a)=a+1$. Also, we note that $\sigma(p^a)=1+p+p^2+\cdots+p^{a-1}+p^{a}=\frac{p^{a+1}-1}{p-1}$ (the sum of terms in a geometric progression).

Theorem: Let the positive integer $n$ have prime factorization $n=p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s}$. Then we have that $$\sigma(n)=\frac{p_1^{a_1+1}-1}{p_1-1}\cdot\frac{p_2^{a_2+1}-1}{p_2-1}\cdot\cdots\cdot\frac{p_s^{a_s+1}-1}{p_s-1}=\prod_{j=1}^s\frac{p_j^{a_j+1}-1}{p_j-1},\tag{4}$$ and $$\tau(n)=(a_1+1)(a_2+1)\cdots(a_s+1)=\prod_{j=1}^s(a_j+1).\tag{5}$$ Proof. Since $\sigma$ and $\tau$ are both multiplicative, we can see that $$\sigma(n)=\sigma(p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s})=\sigma(p_1^{a_1})\sigma(p_2^{a_2})\cdots\sigma(p_s^{a_s}),$$ and $$\tau(n)=\tau(p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s})=\tau(p_1^{a_1})\tau(p_2^{a_2})\cdots\tau(p_s^{a_s}).$$ Inserting the values for $\sigma(p_i^{a_i})$ and $\tau(p_i^{a_i})$ found in $(2)$ and $(3)$, we obtain the desired formulas.

Example: Calculate $\sigma(200)$ and $\tau(200)$.

Solution. Using $(4)$ and $(5)$, we have that $$\sigma(200)=\sigma(2^35^2)=\frac{2^4-1}{2-1}\cdot\frac{5^3-1}{5-1}=15\cdot 31=465,$$ and $$\tau(200)=\tau(2^35^2)=(3+1)(2+1)=12.$$

For your observation specifically, calculating $\sigma(12)$ and $\tau(12)$ yields the following:

• $\displaystyle \sigma(12)=\sigma(2^23^1)=\frac{2^3-1}{2-1}\cdot\frac{3^2-1}{3-1}=7\cdot 4=28$.
• $\tau(12)=\tau(2^23^1)=(2+1)(1+1)=3\cdot 2 = 6$.
• This is pitched at completely the wrong level! Are you really expecting the OP to benefit from this? Commented Jan 25, 2015 at 13:38
• Actually yes, I was (obviously I would not take the time to write it all up, otherwise); however, after having looked at the OP's age and question history, I would have to concur with you. In my defense, the OP has > 500 rep and the question was tagged with number-theory. In my mind, that warrants at least a suitably theoretical response; even my response was probably not "deep" or "sophisticated enough" to fall under the number-theory tag but the elementary-number-theory tag. Hopefully others will benefit from my post though; I do not look at the question history of everyone I answer. Commented Jan 25, 2015 at 14:55
• Yes of course it helped me a lot, I asked this question yesterday but didn't get answer, so thanks.........+1 Commented Apr 25, 2016 at 14:29

Let $$x = \prod_{i=0}^n p_i^{e_i}$$

where the $p_i$ are distincts primes. Then the divisors of x are of the form

$$\displaystyle \prod_{i=0}^n p_i^{t_i}$$

where $0 \leq t_i \leq e_i$.

To get any divisor you have to choose each $t_i$ in $\{0, \ldots, e_i\}$, so for $t_0$ you have $e_0 + 1$ choices and so on, therefore $x$ has

$$\prod_{i=0}^n (e_i + 1)$$

divisors.

Let's take your example of $12$.

$12=2^2\cdot 3^1$

Looking at those two prime powers in turn

• $2^2$ has factors of $2^0, 2^1, 2^2$
• $3^1$ has factors of $3^0, 3^1$

To make all the factors of $12$, we make a factor choice from each of the prime power factors and multiply them together. If we're omitting one of the primes altogether we just choose the zero power - $1$ - for that particular factor:

$$\begin{array}{|c|c|} \hline & 2^0 & 2^1 & 2^2\\ \hline 3^0 & 1 & 2 & 4 \\ \hline 3^1 & 3 & 6 & 12 \\ \hline \end{array}$$

So the exponents on the primes factors feed in to the count of factors in the way you described.

This also gives a quick way to sum all the factors of a number. We just add up all the factors of each prime separately and multiply the results together, so the factors of 12 sum to $(1+2+4)(1+3) = 7\times 4 = 28$.

Let's consider an example for 12. We know that $$12 = 2^2\cdot 3^1.$$ Now observe the following expression: $$({2}^{0} + {2}^{1} + {2}^{2}) \cdot ({3}^{0} + {3}^{1}).$$ As you can see, each of the terms achieved after expanding is a divisor of $12$.

And hence the formula for the number of divisors $= (3)(2) = (2 + 1)(1 + 1) = 6$.

You can try this for any number.

• How to do the Latex thing? Commented Jan 25, 2015 at 13:14
• Try to write what you want to be LateX between two dollar symbols : \$ Commented Jan 25, 2015 at 14:36
• @L16H7 For guidelines concerning LaTeX, check this out: meta.math.stackexchange.com/questions/5020/… Commented Jan 25, 2015 at 15:02