Vtyjkyuk

Suppose we have the number $36$, which can be broken down into ($2^2$)($3^2$). I understand that adding one to each exponent and then multiplying the results, i.e. $(2+1)(2+1) = 9$, yields how many divisors the number $36$ has. I can make sense of a number which can be expressed as the product of two powers of the same prime, i.e. $343$, because $7^3$ allows us to see that: $7$ is a divisor, $7^2$ is a divisor, and the always present $1$ and $343$ are divisors, leaving us with a total number of $4$ divisors for $343$. What is the best way to gain intuition behind using this method for a number like $36$?

If $d$ divides $36$, then no prime numbers other than $2$ and $3$ can divide $d$. On the other hand, $36=2^23^2$ and so $d=2^alpha3^beta$, with $alpha,betain0,1,2$. Since there are three possibilities for $alpha$ and another $3$ for $beta$, there are $9(=3times3)$ possibilities for $d$.

For 36 all the divisors are of the form $2^s3^k$, where $0 le s,k le 2$. Thus as you have 3 choices for each exponent the number of divisors is $3 cdot 3 = 9$.

You're looking for the amount of distinct, positive divisors of 36. To generate all combinations of possible divisors, you do the following:

You take each of 2^0, 2^1, and 2^2 and multiply it by each of 3^0, 3^1, and 3^2. That will give you every divisor, e.g. 1, 2, 3, 4, 6, 9, 12, 18, and 36. There are 9 of these numbers. If you have a collection of m distinct objects M (e.g. the numbers 1, 2, and 4), and another set of n distinct objects N (e.g. 1, 3, and 9), then the total number of ways that you can combine one object from the M collection with one object from the N collection is M * N.

It must be certain that there is no repetition of pairs of factors; for instance if collection M contained both the numbers 2 and 3, and collection N contains the numbers 2 and 3, then there would be 2 different ways of producing 2 * 3 = 6, and then the number 6 would be double-counted. But this problem is avoided, because each collection contains only a particular kind of prime divisor, i.e. all powers of 2 in one collection, all powers of 3 in another collection, all powers of 5 in a different collection, and so on.

To generalize, if you have any number of collections, given that each collection contains no duplicate objects, and given that each collection is partitioned to contain powers of a different prime number, then the total number of combinations you can form by selecting one object from each collection (and multiplying them) is just the product of number of objects in each collection.

If a prime factorization contains some prime p to the N power, the reason why you add 1 to the power of that prime number is that is cardinality (size) of the set of all powers from 0 to N. I.e. that is the number of things in the set (p^0, p^1, p^2, ..., p^N).

So for the number 180, with prime factorization (2^2)(3^2)(5), you can partition the powers of its divisors by primes as 2^0, 2^1, 2^2, 3^0, 3^1, 3^2, 5^0, 5^1. Then the number of combinations of products you can form from these three partitions is 3 * 3 * 2 = 18; which is also (2+1)(2+1)(1+1).

Let's say $$n = p_1^alpha_1 p_2^alpha_2 p_3^alpha_3 ldots$$ where the $p$ are distinct primes, and the $alpha$ are not necessarily distinct and may be $0$ as needed. In your case of $n = 36$, we can have $p_1 = 2, p_2 = 3$, $alpha_1 = alpha_2 = 2$ and all other $alpha_i = 0$. When $alpha_i = 0$, the corresponding $p_i$ does not contribute anything new to the divisors of $n$.

If $alpha_i > 0$ then $p_i$ contributes the following divisors: $1, p_i, p_i^2, ldots, p_i^alpha_i$. Of course with a number like $36$ you also have to account for divisors like $p_1 p_2^2$.

The more general case is for a composite of the form $$n = prodlimits_k = 1^k_max p_1^a_1 p_2^a_2 ldots p_k_max^a_k_max,$$ where the $p_k$ are unique primes and the corresponding $a_k$ the exponents. In this case the number of factors is $$(a_1+1)(a_2 + 1) ldots (a_k_max+1) = prodlimits_k=1^k_max (a_k + 1)$$