Number of Relatively Prime Factors

Question

Given a number $n$, in how many ways can you choose two factors that are relatively prime to each other (that is, their greatest common divisor is 1)?

Also, am I going in the correct direction by saying if $n$ is written as $p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$, where $p_i$ is a prime and $a_i\geq 1$, then the number of factors $n$ has is $(a_1 + 1)(a_2 + 1)\dots (a_k + 1)$, and when I choose a factor $x = p_1^{b_1}p_2^{b_2}\dots p_k^{b_k}$, the number of factors is $(c_1 + 1)(c_2 + 1)\dots (c_k + 1)$, where $c_i = 0$ if $b_i\neq 0$ and $c_i = a_i$ otherwise?

Answer 1

We interpret the question as asking for the number of unordered pairs of (distinct) divisors of $n$ that are relatively prime. For me it is easier to think in terms of ordered pairs.

So we are producing an ordered pair $(x,y)$ of relatively prime divisors of $n$. Examine one after the other the primes $p_i$. At each prime we have three types of choices: (i) assign $p_i$ to $x$; (ii) assign it to $y$; (iii) assign it to neither. If we assign $p_i$ to $x$, it can be done in $a_i$ ways, for the power of $p_i$ is at our disposal. Same with $y$. And we can assign to neither in $1$ way,for a total of $2a_i+1$. Thus the total number of ordered pairs is $P$, where $$P=\prod_1^k(2a_i+1).$$ This includes the ordered pair $(1,1)$. Now for unordered pairs of distinct relatively prime divisors, there are $\frac{P-1}{2}$ possibilities.

Remark: If we want the product of the two factors to be $n$, the counting becomes much simpler. For ordered pairs, we choose a subset of the set of primes, and assign $p_i^{a_i}$ in the chosen subset to $x$, and assign the rest to $y$. There are $2^k$ ways of choosing $x$, and then $y$ is determined. So there are $2^k$ ordered pairs, and for $n\gt 1$, there are $2^{k-1}$ unordered pairs.

Answer 2

Separating it into a number of distinct primes is the correct direction; from there you've gone off course. While you could try generating or counting all the factor pairs of $n$, it isn't going to help you: there's a way of generating the relatively prime factor pairs that doesn't involve any checking to see whether they're actually relatively prime.

HINT If two numbers $a,b$ are relatively prime to one another, what can you say about the presence of a prime $p$ in the factor lists of these two numbers? what does that tell you about relatively prime factor pairs of a given number $n$?