2
$\begingroup$

I was trying to figure out the number of positive divisors of large numbers and came across something interesting.

I'm not sure whether this is a theorem that already exists, it probably does and I've just never come across it.

So if you consider the prime factor $1 000 000$,

That's $10^6= (5\times2)^6 = 5^6 \times 2^6$

Now this is as simplified product of prime factors you can get for $1 000 000$.

I manually calculated the number of positive divisors there are for $1 000 000$ and I figured out that there were $49$ of them.

What I noticed however, was $49$ was the $(6+1) \times (6+1)$, 6 being the powers of the simplified product of prime factors.

Now I let this be to coincidence but I tried it for another number.

The prime factors of $315 000$

$315 \times 10^3 = 63 \times 5 \times 5^3 \times 2^3$ = $9 \times 7 \times 5^4 \times 2^3$

When you manually calculate the number of prime divisors, you obtain $120$, which is also the product of $(3+1)(2+1)(4+1)(1+1) = 120, 3,2,4$ and $1$ being the powers of the product of prime factors.

Now, does this apply to all prime factorisations and number of divisors or am I looking silly and just stating a well-known theorem or is this is just a massive coincidence?

This possibly involves a hint of combinatorics. Any explanation is appreciated!

$\endgroup$
  • $\begingroup$ Yes, this is a known result - multiply together one more than each distinct prime exponent for the number of factors. Good discovery work. $\endgroup$ – Joffan Jan 2 '17 at 21:18
  • $\begingroup$ Thanks! Is there a reason to why it works or does it just simply work? $\endgroup$ – TripleA Jan 2 '17 at 21:19
4
$\begingroup$

In order to generate each factor of a number $n = \prod p_i^{k_i}$, you need to select a power from each dividing prime to multiply in to that factor. For each dividing prime $p_i$ with exponent $k_i$, you have $k_i+1$ choices. These are all independent choices so the total number of factors is as you have found, $\prod (k_i+1)$.

$\endgroup$
  • 1
    $\begingroup$ Mmmm i see where the combinatorics comes in now, thanks a lot, but I seem like an idiot for asking ;) $\endgroup$ – TripleA Jan 2 '17 at 21:26
  • 1
    $\begingroup$ Not at all, it's great to find these things out independently. Bonus fact - this shows why only square numbers have an odd number of factors. $\endgroup$ – Joffan Jan 2 '17 at 21:27
3
$\begingroup$

This is known as one of the divisor functions, the one that sums the zeroth powers of the divisors. Taking your example of $315000$, the divisor can have anywhere from $0$ to $3$ powers of $2$, which is four choices, and so on for the other factors. It is a well known and useful result in number theory. If you search the site for divisor function you will find many questions that use it.

$\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.