0
$\begingroup$

This question already has an answer here:

This could be a classic problem or my wording might be totally off, but I can't seem to find an answer to this problem:

Given $n\in\mathbb{Z}$ with prime factorization $n=p_1^{q_1}\dots p_m^{q_m}$, how many integers divide $n$? For the sake of this problem, let's ignore $1$ and $n$ until the end.

First off, we have that there are at least $q_1\dots q_n$ divisors, since there are $q_1$ divisors made up of $p_1$ (namely $p_1,p_1^2,\dots,p_1^{q_1}$), thus the same holds for $p_2,\dots,p_n$

I've never done much with combinatorics, so I'm not quite sure how to begin counting unique divisors by mixing and matching distinct primes. Any thoughts?

$\endgroup$

marked as duplicate by user91500, Joey Zou, naslundx, Dietrich Burde, Claude Leibovici Sep 15 '16 at 9:25

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

Let $n=p_1^{q_1}\dots p_m^{q_m}$. Then we see that the divisors of $n$ that are powers of $p_1$ will be:

$1, p_1, p_1^2, p_1^3, ..., p_1^{q_1}$

The divisors of $n$ that are powers of $p_2$ will be:

$1, p_2, p_2^2, p_2^3, ..., p_2^{q_2}$

And so on.

What we notice is that any factor of $n$ (including $1$ and $n$) can be generated by taking exactly one number from each of the prime factor power sequences and multiplying them all together. There are $q_1+1$ numbers in the $p_1$ sequence, $q_2+1$ numbers in the $p_2$ sequence, etc. Therefore, we see that there are $(q_1+1)\times...\times(q_n+1)$ factors of $n$.

$\endgroup$

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