0
$\begingroup$

I am reading a math book. It states the following rule:

For an integer $n$ greater than 1, let the prime factorization of $n$ be $$n=p^a_1p^b_2p^c_3...p^m_k$$ Here $a, b, c,..., m$ are nonnegative integers, and $p_1,p_1,...,p_k$ are prime numbers. Then the number of divisors of $n$ is: $$d(n)=(a+1)(b+1)(c+1)...(m+1)$$

I can use the rule to solve problems correctly, but I don't understand the rule. How to prove it?

$\endgroup$
  • $\begingroup$ It might be helpful to your future Readers to be told what "math book" you were reading (author and title, etc.). $\endgroup$ – hardmath Jun 2 '16 at 0:57
  • 1
    $\begingroup$ Try it. If n = p then the factors are 1 and p. If the number is $p^n$ the factors are 1, p, $p^2,....p^n $. That's n +1 factor. If the number is $p^nq^m $ the factors are 1$,p,p^2...., p^n $ and $q,q^2,...q^m $ and every combination $p^iq^j $. There are n+1 choices I can be (1,... n) and m+1 choices j can be (1,....m). So there are (n+1)(m+1) factors total. These can be extended if the number has more prime factors. $\endgroup$ – fleablood Jun 2 '16 at 1:05
1
$\begingroup$

Note: This is not a proof, but an explanation. I misread the question. I hope this helps anyway.

First, I will explain what, AFAIK, is a more common version of prime factorization (which is what the rule in your question is): any positive integer greater than one can be expressed as the product of one or more prime numbers, where there can be multiple of any of the prime numbers. Prime numbers are their own prime factorizations. Composite numbers have multiple numbers in their prime factorizations. For example, the prime factorization of $7$ is $7$, because $7$ is prime. The prime factorization of $4$ is $2*2$. Most composite number have much larger prime factorizations, such as $5280$, whose prime factorization is $2*2*2*2*2*3*5*11$.

Now for the version in your question. Let's go back to the prime factorization of $5280$. See all those $2$s? Those could be expressed as a power, so the new version is $2^5*3*5*11$. Each number there has its degree (in your question, the variables $a$ through $m$). In fact, you can think of $2^5*3*5*11$ as $2^5*3^1*5^1*11^1$. Then $a$ is $5$ and $b$, $c$ and $d$ are 1. Now you can think of $p_k$ as one of those prime numbers (obviously replacing $k$ with the number you are referring to), and $a$ through $m$ as their degrees (powers).

$\endgroup$
2
$\begingroup$

A divisor of $n$ is of the form $d=p_1^{i_1}\cdots p_{k}^{i_k}$ where

$0\leq i_1\leq a$,
$0\leq i_2\leq b$, etc.

By fundamental theorems, a divisor is uniquely specified by the sequence $(i_1,\cdots,i_k)$, with no two different divisors having the same sequence. Thus to specify a divisor, you just need to specify the power $i_k$ of each of its prime factors. There are $(a+1)$ choices for $p_1$ (you can pick $i_1=0$), and so on. That's where you get the product.

$\endgroup$
1
$\begingroup$

If a number has prime factors $p_1^a,p_2^b......,p_k^m$ then we would find the number of divisors as follows:-
$[$ (None of $p_1$) or ($1$ of $p_1$) or ($2$ of $p_1$) ..............or ($a$ of $p_1$) $]$ $\times $ $[$(None of $p_2$) or ($1$ of $p_2$) or ($2$ of $p_2$) ..............or ($b$ of $p_2$)$]$$\times$.........................$\times $ $[$(None of $p_k$) or ($1$ of $p_k$) or ($2$ of $p_k$) ..............or ($m$ of $p_k$)$]$ $\tag{1.}$

Here Each operand of 'or' states one possibility of a divisor so for $p_1$ ,there are ($a+1$) possibilities ,for $p_2$ ,($b+1$) possibilities and so on.......
So by fundamental principle of counting there are $(a+1)\times(b+1).......\times(m+1)$ possible divisors.

$\endgroup$

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.