[Math] Counting the number of distinct greatest common divisors for an integer.

Question

What is the expression for the number of distinct greatest common divisors possible for the number $N$? Let us say that $N$ is composed of 4 prime numbers $N = p_3 p_2 p_1 p_0$. Now if $p_i$ are all unique, I think the answer is
$$
C = \sum_{i = 0}^4 {4 \choose i}
$$
I can also tell that there are less than this if a prime repeats, say $p_3 = p_2$ (by enumerating by hand).

Answer 1

You are essentially asking for the number of positive divisors of $N$. If $$N=p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n},$$ where the $p_i$ are distinct primes, the number of positive divisors of $N$ is $$(a_1+1)(a_2+1)\cdots(a_n+1).$$

For to make a positive divisor of $N$, we first sit in front of the prime $p_1$, and decide how many copies of $p_1$ the positive divisor will get. Our choices are $0$, $1$, and so on up to $a_1$, a total of $a_1+1$ choices. Now we sit in front of $p_2$, and decide on how many copies of $p_2$ the divisor will get. There are $a_2+1$ choices. And so on.

The result uses the fact that any positive integer has an essentially unique representation as a product of prime powers.