Given a number $N$, and i know the Multiplicity of all of its prime factors, such that
$$N = 2^a \cdot 3^b \cdot 5^c \cdots p^k$$
so that $a+b+c+\cdots+k = X$
where $p$ is the largest prime factor of $N$, i want to calculate the number of factor pair $(i, j)$ (prime + non-prime) i can from these prime factors of $N$, such that $ij = N$
i have been doing this for two hours but couldn't get anywhere, it just gets so complex that i fail. but somehow i feel it shouldnt be too complex.
i was thinking of permutation/combination, like dividing K type of balls into two boxes where we can have more then one balls for each type.
please help me.
please re-tag if you have more appropriate tags for this.
Best Answer
Note: A solution was given many hours ago by Bill Cook, under the assumption that what was asked for is the number of unordered pairs. This was then modified to deal with ordered pairs, and then, for reasons not clear to me, deleted.
We want to count the number of ordered pairs $(i,j)$ such that $i$ and $j$ are positive integers and $ij=N$. Let $X$ be this collection of ordered pairs, and let $Y$ be the set of positive divisors of $N$. Then the number of ordered pairs is the same as the number of positive divisors. This is essentially obvious, so the next paragraph need not be read!
To be formal about it, define the map $\varphi\colon X\to Y$ by $\varphi(i,j)=i$. Then the map $\varphi$ is a bijection. This is not hard to verify. For example, to show that $\varphi$ is onto, let $i$ be any element of $Y$.
Let $j=N/i$. Then $\varphi(i,j)=i$.
Our count of the number of divisors uses the Fundamental Theorem of Arithmetic, aka the Unique Factorization Theorem: Every positive integer has, apart from the order of the terms, a unique representation as a product of prime powers. (The positive integer $1$ is represented as the empty product.)
We show how we can build divisors of $N$ step by step. Imagine the following cafeteria line. First there is a tray with $a$ $2$'s. Next comes a tray with $b$ $3$'s, and then a tray with $c$ $5$'s, and so on, with finally $k+1$ $p$'s. It is OK if some of the trays are empty, for example if $a=0$.
We build a divisor $d$ of $N$ as follows. Go down the cafeteria line. First choose the number of $2$'s that $d$ will "have." More formally, we are choosing the exponent of $2$ in the prime power factorization of $d$. There are $a+1$ possible choices, namely $0,1,\dots,a$.
Continue down the cafeteria line. For every decision about the number of $2$'s, there are $b+1$ ways to decide on the number of $3$'s that $d$ will have. Thus there are $(a+1)(b+1)$ ways to decide on the number of $2$'s and the number of $3$'s.
Continue. For every decision about the number of $2$'s and the number of $3$'s, there are $c+1$ ways to decide on the number of $5$'s that $d$ will have, and so on. Continue. We conclude that the number of positive divisors of $N$, and hence the number of ordered pairs, is equal to $$(a+1)(b+1)(c+1)\cdots (k+1).$$
Comment $1$: The notation that uses the alphabet in increasing order, as in the current post, used to be standard. That is how Euler wrote. Nowadays indices are ordinarily used, with in my opinion a loss of clarity. With indices, the result would be stated as follows. Suppose that $$N=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}=\prod_{i=1}^k p_i^{e_i},$$ where the $p_i$ are distinct primes, and the $e_i$ are positive (or even non-negative) integers. Then the number $d(N)$ of positive divisors of $N$ is given by $$d(N)=(e_1+1)(e_2+1)\cdots(e_k+1)=\prod_{i=1}^k (e_i+1).$$
Comment $2$: There is a slightly different point of view that is very useful in the long run. For any positive integer $n$, let $d(n)$ be the number of positive divisors of $n$. It can be shown that if $a$ and $b$ are relatively prime (meaning that they have no common positive divisor greater than $1$), then $d(a,b)=d(a)d(a)$. [A function $f$ defined on the positive integers is called multiplicative if $f(a,b)=f(a)f(b)$ whenever $a$ and $b$ are relatively prime.] Since the function $d(n)$ is multiplicative, if we know $d(p^e)$ for any prime power $p^e$, we know $d(n)$ for any positive integer $n$. But it is clear that $d(p^e)=e+1$.