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.
$\endgroup$ 24 Answers
$\begingroup$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$.
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.
$\endgroup$ $\begingroup$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$.
$\endgroup$ $\begingroup$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.
$\endgroup$ 3
