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?


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.

  • $\begingroup$ I'm not sure that choice (iii) is actually intended to be available here: I was under the impression that you're looking for two numbers that multiply to $n$, that are relatively prime. $\endgroup$ – Dan Uznanski Oct 3 '14 at 15:40
  • 1
    $\begingroup$ I am not sure either. The "two factors" wording, strictly speaking, does not force the product of the two factors to be $n$. However, product $n$ may very well have been intended. $\endgroup$ – André Nicolas Oct 3 '14 at 15:47
  • $\begingroup$ No, I didn't intend that the product of the two factors be $n$. Thanks for a great answer! $\endgroup$ – shardulc Oct 3 '14 at 16:09
  • $\begingroup$ You are welcome. $\endgroup$ – André Nicolas Oct 3 '14 at 16:30

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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