Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
5  
Do you mean ordered pairs $(i,j)$ such that $ij=N$? Then we are talking simply about the number of divisors, which is $(a+1)(b+1)\cdots(k+1)$. –  André Nicolas Jan 6 '12 at 0:32
    
@Pheonix could you un-accept my answer? It should be deleted given several flaws. Andre's original answer in the comment is what you're looking for (i.e. ordered pairs). –  Bill Cook Jan 6 '12 at 0:50
    
@BillCook done. –  Pheonix Jan 6 '12 at 1:10
    
@Pheonix thanks! –  Bill Cook Jan 6 '12 at 2:45
    
@AndréNicolas Please add your comment as an Answer so i can mark it accepted. –  Pheonix Jan 6 '12 at 15:01
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
    
That was a very clear explanation. Thank you. Why does an Approach of 2^(total count of factors) work ? For every factor of the N, it has two choices, either to get multiplied by I or by J, but this gives wrong answer, I am sure you can clear my doubt here. –  Pheonix Jan 6 '12 at 18:58
    
@Pheonix: I am guessing about what you mean. Take a prime divisor $p$ of $N$, and suppose $p^e$ is the largest power of $p$ that divides $N$. If $e>1$, we have more than $2$ choices, for we can give some of the $p$'s to $i$ and the rest to $j$, it is not necessarily "all or nothing." But there is an interesting question in which your proposed answer is correct. Suppose that we want to count the number of ordered pairs $(i,j)$ such that $ij=N$ and $i$ and $j$ are relatively prime. Then if $N$ has $k$ distinct prime divisors, the number of such ordered pairs is indeed $2^k$. (Cont) –  André Nicolas Jan 6 '12 at 19:09
    
(Cont) As a simple example, let $N=72=2^3\cdot 3^2$. Then there are $(3+1)(2+1)$ ordered pairs $(i,j)$ such that $ij=72$. But there are $(2)(2)$ ordered pairs $(i,j)$ such that $ij=72$ and $i$ and $j$ are relatively prime. –  André Nicolas Jan 6 '12 at 19:12
    
why does this approach fails for when we are looking for all factors ? 72 = 2^3 . 3^2 ... so first '2' has two choices, second 2 has 2 choices, third 2, and both 3s.. so 2^(3+2) (this was my initial approach to the question, and i fail to identify why is this wrong )? –  Pheonix Jan 6 '12 at 19:18
1  
You are thinking of the $2$'s as somehow distinct. Think of your counting method, in which you say yes to the "first" $2$, not the second, yes to the third. Now you say no to the first, yes to the second, yes to the third. These are counted as different choices in your count. But they result in the same factor of $72$, namely $4$. Your initial approach overcounts by quite a bit. –  André Nicolas Jan 6 '12 at 20:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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