# How many ways a composite number can be resolved into two factors which are prime to each other?

Let N denote the number, and suppose $N=a^p \times b^q \times c^r \cdots$, where $a,b,c,\cdots$, are different prime numbers and $p,q,r,\cdots$ are positive integers.Then it is clear that each term of the product

$$(1+a+a^2+\cdots+a^p)(1+b+b^2+\cdots+b^q)(1+c+c^2+\cdots+c^r)\cdots$$

is a divisor of the given number,and that no other number is a divisor; then how could we use this to show/find that the number of ways in which this $N$ can be resolved into two factors which are prime to each other is $2^{n-1}$,where $n$ is the number of different prime factors in $N$?

-
The terms in your product do list all the divisor, but that doesn't really help here. Notice that you cannot use $a^i$ in one factor and $a^{p-1}$ in the other, unless $i=0$ or $i=p$, because then the two factors will share a power of $a$ as a common factor. – Jyrki Lahtonen Nov 9 '11 at 17:28
@Jyrki Lahtonen:I found this approach in this book but it's a bit abstruse (for me). – Quixotic Nov 9 '11 at 17:31

We obtain all ordered pairs $(x,y)$ such that $xy=N$ and $\gcd(x,y)=1$ by choosing a subset of the set of prime divisors of $N$, and giving all these primes to $x$, and giving the rest of the primes to $y$. A set of $n$ elements has $2^n$ subsets, so there are $2^n$ ways to produce a suitable $x$, and hence $2^n$ ordered pairs $(x,y)$.

We now have a count of the ordered pairs. But we want to count the number of factorizations as a product of two relatively prime numbers, and for example $(20)(3)$ is considered to be the same factorization as $(3)(20)$. For $n\ge 1$, to count the unordered pairs, divide the number of ordered pairs by $2$. We get $2^{n-1}$. For a more familiar example, there are $(52)(51)$ ordered pairs of $2$ cards, but there are only $(52)(51)/2$ "hands" of two cards.

The only case where we do not divide by $2$ is the case $N=1$, that is, $n=0$, where the only factorization is $(1)(1)$. So the exact result is that the number of factorizations of the desired type is $2^{n-1}$ if $n\ge 1$ and $1$ if $n=0$.

Comment: Consider the product $$(1+a+a^2+\cdots+a^p)(1+b+b^2+\cdots+b^q)(1+c+c^2+\cdots+c^r)\cdots \qquad(\ast)$$ Look at a typical full term $1+p+p^2+\cdots +p^k$. We produce the suitable divisors $x$ of $N$ by deciding whether we will use the $1$ or the $p^k$. No other choice is possible, because if we choose $p^i$ where $0<i<k$, then $N/x$ (in our notation, $y$) will be divisible by $p$, so $x$ and $y$ will not be relatively prime.

Thus at every term in the product $(\ast)$, we have $2$ choices, "None" or "All." There are $n$ terms in the product, so there are $2^n$ ways to produce $x$. Now argue as before that if $n \ge 1$, every suitable factorization is produced twice by this process.

-
The key is that all the $a$'s have to go into one factor, otherwise the two factors would not be prime to each other. – Ross Millikan Nov 9 '11 at 17:30
+1;However,I understood the explanation by linking the comment with the above;Edit:now got in both ways:) – Quixotic Nov 9 '11 at 18:29
@MaX: That's why I added the comment. I really prefer to think of it as follows. Let $N=p_1^{e_1}p_2^{e_2}\cdots p_k^{e^k}$, where the $p_i$ are distinct primes. To build $x$, we sit in front of $p_1$ and decide whether $x$ should get all the $p_1$s or none. Then we move on to $p_2$, all or none, and so on. – André Nicolas Nov 9 '11 at 18:45
Nicely explained. (+1) – robjohn Nov 9 '11 at 18:57