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.

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

share|improve this question
    
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

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
    
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
2  
@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

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.