# How can I solve this combinatorics problem more efficiently?

I was asked to prove that there are 7 different ways of expressing the number 63000 as the product of two coprimes which are larger than 1.

My solution consisted in decomposing 63000 into its prime factors ($2^3*3^2*5^3*7^1$) and, since two coprimes cannot share their factors, grouping the factors into all possible combinations as following:

1. $2^3$ & $3^2*5^3*7^1$
2. $3^2$ & $2^3*5^3*7^1$
3. $5^3$ & $2^3*3^2*7^1$
4. $7^1$ & $2^3*3^2*5^3$
5. $2^3*3^2$ & $5^3*7^1$
6. $2^3*5^3$ & $3^2*7^1$
7. $2^3*7^1$ & $3^2*5^3$

There are 7 combinations, therefore 63000 can be expressed as the product of two coprimes in 7 different ways.

The problem with this solution is that I had to use brute force to find all the combinations. If the number had not been 63000 but another one with n factors, finding the solution could have been much harder. What is the correct way of finding the solution using combinatorics?

• Actually, you missed the product 63000=1*63000. The solution is linked to the number of subset of the primes in 63000. Dec 14, 2017 at 19:42
• Yes, sorry I'll correct it now.
– OCA
Dec 14, 2017 at 19:44

you want something you can generalize.

$A = \{2,3,5,7\}$ is the set of prime elements in the factorization of $63,000.$

The "Powerset of $A$" is the set of all subsets of $A.$ And the number of elements in the powerset of a set with $n$ elements is $2^n$ (this includes the empty set and the entire set)

The co-prime factor pairs of 63000 can be thought of a subset of $A$ times the complimentary subset of $A$

The number of pairs is $\frac 12 2^4 = 8$

However, you then have the additional rule not to count $63,000\cdot 1$ in your set of factor pairs.

And for any number then, $2^{n-1} - 1$

You can't really do this without factoring the number, or at least determining what its prime factors are (or, what probably amounts to the same thing, how many distinct prime factors it has). Once you have that information, though, suppose that the distinct primes dividing $n$ are $p_1, p_2, \dotsc, p_k$. Then one factor must have all factors of $p_1$, one must have all factors of $p_2$, and so forth.

So for each of $p_1, p_2, \dotsc, p_k$, pick a factor (factor 1 or factor 2) in two different ways. There are thus $2^k$ combinations of choices. But this counts each factorization twice (for example, in your case, you'd get both $2^3$, $3^2\cdot 5^3\cdot 7$ and $3^2\cdot 5^3\cdot 7$, $2^3$. So you must divide $2^k$ by $2$, giving $2^{k-1}$ possibilities, where $k$ is the number of distinct prime factors of $n$.

If you wish to exclude the case where the smaller factor is $1$, then the answer is $2^{k-1}-1$.