4
$\begingroup$

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

  • 0
    @Jyrki Lahtonen:I found this approach in this [book](http://www.amazon.com/HIGHER-ALGEBRA-HALL-KNIGHT/dp/B000PH9PFO) but it's$a$bit abstruse (for me).2011-11-09

1 Answers 1

11

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

  • 0
    Nicely explained. (+1)2011-11-09