How many ways are there to factor a number so that the factors are relatively prime?

Question

Sorry while preping for finals I stumbled upon this problem. Does the answer involve using Euler's Totient Function?

Integers a and b are relatively prime if gcd(a,b) = 1. How many ways can we factor 88,200 so that the factors are rela-tively prime?

Answer 1

$N = 88200 = 2^3 \cdot 3^2 \cdot 5^2 \cdot 7^2$. So any way we write $N = ab$ with $\gcd(a,b) = 1$, we build $a$ and $b$ from disjoint prime sets from $\{2,3,5,7\}$. There are $2^4$ ways to pick the primes for $a$ (and then we include the full power of that prime, as $b$ cannot have it as a divisor) and then $b$ is determined uniquely. So 16 different ways, as $N$ has 4 distinct prime divisors. This includes $1\cdot N$, which you might want to rule out. I that case, there are 14 ways left. If order does not matter we overcount by 2, so for $k$ prime factors we are left with $2^{k-1} -1$, if we discount the ones with a 1.

If order does not matter and we consider any number of factors, unequal to 1: we again look at the number of ways we can partition the set of primes:

$\{2\}, \{3\}, \{5\}, \{7\}$ is one, $\{2,3\}, \{5,7\}$ another. Just enumerate those and take their powers to get all those factorisations. In general we thus need the Bell number of $n$ if we have $n$ many prime factors. This counts the number of partitiions of a set of $n$ members into non-empty subsets.

This disregards sign (just positive numbers and no 1's).

Answer 2

For this preoblem you need only consider the prime divisors of $n$, i.e., without their exponent. If $n$ is divisible by $k$ different primes, then we can pick any subset of this $k$-set and multiply the powers of these primes together to obtain $a$ and similarly obtain $b$ from the rest. As there are $2^k$ subsets of a $k$-element set, ...

Note that if $a,b$ are only required to be integers as opposed to positive integers, the number of solutions doubles.

Answer 3

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. Hope you can take it from here.