11
$\begingroup$

I've been trying to find / generate a formula for the following problem:

  • Given a number, how many positive integers are factors of this number.

In practice, you could simply build a table as such (lets assume the number is 36):

1 | 36
2 | 18
3 | 12
4 | 9
6 | 6

Thus there are 9 positive integers that are factors to 36.

This method seems like it would be taxing if the number was large. So I was thinking that if you knew the prime factorization for a number such as $\,2 \cdot 2 \cdot 3 \cdot 3 = 36, \,$ there should be a formula for the number of unique combinations you can multiply these prime factors together. That's where I am stuck. Thanks in advance!

$\endgroup$
2
  • 2
    $\begingroup$ mathworld.wolfram.com/DivisorFunction.html $\endgroup$ Commented Feb 5, 2013 at 14:41
  • $\begingroup$ Well, good thinking. Consider just the power of a prime, let's say 2^5 with factors 2^0, 2^1, 2^2, 2^3, 2^4, 2^5. 6 factors. p^k has (k + 1) factors. If you have multiple primes, each combination of factors of the prime powers gives a unique factor. So 2^2 * 3^2, 3 factors of 4, multiplied by the 3 factors of 9, gives 3 * 3 = 9 factors. $\endgroup$ Commented May 15, 2014 at 16:51

6 Answers 6

Reset to default
13
$\begingroup$

Hint: if the prime factorization of $\,n\in\Bbb N\,$ is

$$n=\prod_{k=1}^rp_k^{a_k}$$

then the number of divisors of $\,n\,$ is

$$\prod_{k=1}^r(a_k+1)$$

$\endgroup$
4
  • $\begingroup$ Thank you so much! Is there a proof for this I could look at? $\endgroup$ Commented Feb 5, 2013 at 14:49
  • 1
    $\begingroup$ Look at David Pollack's answer to manhattangmat.com/forums/… $\endgroup$ Commented Feb 5, 2013 at 14:57
  • $\begingroup$ @Ross Millikan Oh! That makes alot of sense! I feel so foolish now... Thanks! $\endgroup$ Commented Feb 5, 2013 at 15:05
  • 1
    $\begingroup$ Another source, on this site, is Rich Decker's answer to math.stackexchange.com/questions/295407/… $\endgroup$ Commented Feb 5, 2013 at 15:22
8
$\begingroup$

Consider this: Every positive integer has a unique prime factorisation, so choosing integers is the same as choosing prime factorisations. A prime factorisation divides another prime factorisation if and only if the exponents of each prime in the former are less than or equal to their counterparts in the latter.

So the number of divisors is the number of ways of choosing exponents satisfying that condition. For each prime $p^a$, I can choose any exponent between $0$ and $a$ inclusive – that's $a + 1$ choices. So, in conclusion: if \[n = \prod_{k = 1}^{N} p_k^{a_k}\] then \[\mathrm{\#factors}(n) = \prod_{k = 1}^N (a_k + 1)\]

$\endgroup$
3
  • $\begingroup$ So to speak. $36=2^2.3^2$, then $\phi(n)=(2+1)\times(3+1)$? $\endgroup$ Commented May 28, 2015 at 10:36
  • $\begingroup$ The usual notation is $\tau(n)$ or $d(n)$. The notation $\phi(n)$ is reserved for Euler's function. $\endgroup$ Commented May 28, 2015 at 11:51
  • $\begingroup$ @lhf: thanks, avoided $\endgroup$ Commented May 29, 2015 at 0:39
5
$\begingroup$

Alongside all the other replies here, I want to also offer a more visual/intuitive (at least for myself) explantion.

Consider the number whose prime factorization is: $$2(3^2)5$$

As others have shown, you need to finding the factors of this number involves finding the number of ways the prime factors of this number can be combined. One way is to view each possible exponent of a prime factor as a possible event and build a tree. I thought it would be hard to say it exactly, so below is a picture to describe the process.

https://i.sstatic.net/3ewkN.jpg

Looking at that you can see that the total number of 'events' is the product of all the events possible for each number - which is its exponent + 1 in the prime factorization. In the example above it's (1 + 1)(2 + 1)(1 + 1) = 12.

Once you have the intuition behind it, the formal definition feels a lot more approachable, at least for me. Hope it helps!

$\endgroup$
2
$\begingroup$

Let's say you have a number n. Let $n=\ p_1^r.p_2^m.p_3^n$ then the number of positive factors is (r+1)(m+1)(n+1). (I do not know how to make $r_1,r_2$ in exponent, so I used r,m,n. In your case, 36=$2^2.3^3$ so (2+1)(2+1)=9.

$\endgroup$
3
  • $\begingroup$ To write $p_1^{r_1}$ you write p_1^{r_1} between dollar signs. $\endgroup$ Commented Feb 5, 2013 at 14:56
  • $\begingroup$ In general, in $\LaTeX$ if you put something in braces it gets treated as a single character. So if you want $r^{12}$ you need r^{12} instead of r^12, because the latter gives $r^12$ $\endgroup$ Commented Feb 5, 2013 at 14:59
  • $\begingroup$ Aside from LaTex, please review your answer since it should be 12 not 9 $\endgroup$ Commented Jan 12, 2024 at 4:03
2
$\begingroup$

Given the prime factorization of $m\in\Bbb N$, $$m = \prod_{k = 1}^{n} p_k^{a_k}$$

We want to find the number of $n$-tuples of the Cartesian product of sets $A_1\times A_2\times ... \times A_n$ given by $$A_k=\{p_k^0,p_k^1,...,p_k^{a_k} \}$$

As we can easily see, $$|A_k|=a_k+1$$

Now, if we have $n$ sets $A_1,A_2,...,A_n$, by the rule of product: $$|A_1\times A_2\times ...\times A_n|=|A_1|\cdot |A_2|\cdot\ ...\ \cdot|A_n|$$ $$=(a_1+1)\cdot (a_2+1)\cdot \ ... \ (a_n+1)$$ $$=\prod_{k=1}^n(a_k+1)$$

$\endgroup$
-2
$\begingroup$

Let me explain this with the help of an example. Let the number be 630. Now the prime factorization of $630 = 2^1 × 3^2 × 5^1 × 7^1$. Any factor is a combination of one or more numbers with their power ranging from 0 to maximum.

For 2 , the power can be 0 or 1 i.e. 2 ways. For 3 , the power can be 0 or 1 or 2 i.e. 3 ways. For 5, the power can be 0 or 1 i.e. 2 ways For 7 , same as 5 i.e. 2 ways.

Now if you know basics of permutation and combination, the number of ways we can select any power of the above prime factorization is

2×3×2×2 = 24.

Hence 630 has 24 factors.

Now the formula is Let $N = (A^r)×(B^m)×(C^n)$ where A,B,C are the prime factors of N, then the total number of positive factors of N is given by (r+1)(m+1)(n+1).

$\endgroup$
4
  • $\begingroup$ Note that if you have more than three primes in your decomposition, say $N=p_1^{r_1}\cdots p_k^{r_k}$, then the number or factors is $(r_1+1)\cdots (r_k+1)$. $\endgroup$ Commented May 28, 2015 at 10:33
  • $\begingroup$ @Pierre-GuyPlamondon can you please illustrate that for the number 630 as it would be helpful for me as well as others. $\endgroup$ Commented May 28, 2015 at 10:45
  • $\begingroup$ I've just noticed that this question is rather old, and with a perfectly good (and accepted) answer. Please refer to it. $\endgroup$ Commented May 28, 2015 at 10:49
  • $\begingroup$ @Pierre-GuyPlamondon The accepted answer does does not say anything about the more than 3 primes thing. $\endgroup$ Commented May 28, 2015 at 11:32

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.