10
$\begingroup$

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$
11
$\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$.
$\endgroup$
  • 2
    $\begingroup$ This is pitched at completely the wrong level! Are you really expecting the OP to benefit from this? $\endgroup$ – TonyK Jan 25 '15 at 13:38
  • 2
    $\begingroup$ 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. $\endgroup$ – Daniel W. Farlow Jan 25 '15 at 14:55
  • $\begingroup$ Yes of course it helped me a lot, I asked this question yesterday but didn't get answer, so thanks.........+1 $\endgroup$ – mnulb Apr 25 '16 at 14:29
7
$\begingroup$

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$
7
$\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$
4
$\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$
  • $\begingroup$ How to do the Latex thing? $\endgroup$ – Bhaskar Jan 25 '15 at 13:14
  • 1
    $\begingroup$ Try to write what you want to be LateX between two dollar symbols : $ $\endgroup$ – Pyrofoux Jan 25 '15 at 14:36
  • 1
    $\begingroup$ @L16H7 For guidelines concerning LaTeX, check this out: meta.math.stackexchange.com/questions/5020/… $\endgroup$ – Daniel W. Farlow Jan 25 '15 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.