Question

The number of ways of factoring 91,000 into two factors, $m$ and $n$, such that $m>1,n>1$ and $\gcd (m,n)=1$ is

• A. 7
• B. 15
• C. 32
• D. 37

Answer 1

Answer: (A)

We have $91,000=2^3\times 5^3\times 7\times 13$ Let $A=\left\{2^3,5^3,7,13\right\}$ be the set associated with the prime factorization of 91,000 . For $m,n$ to be relatively prime, each element of $A$ must appear either in the prime factorization of $m$ or in the prime factorization of $n$ but not in both. Moreover, the 2 prime factorizations must be composed exclusively from the elements of $A$. Therefore, the number of relatively prime pairs $m,n$ is equal to the number of ways of partitioning $A$ into 2 unordered non-empty subsets. We can partition $A$ as follows:
$\left\{2^3\right\}\cup \left\{5^3,7,13\right\},\left\{5^3\right\}\cup \left\{2^3,7,13\right\}$
$\{7\}\cup \left\{2^3,5^3,13\right\},\{13\}\cup \left\{2^3,5^3,7\right\}$
and $\left\{2^3,5^3\right\}\cup \{7,13\},\left\{2^3,7\right\}\cup \left\{5^3,13\right\},$
$\left\{2^3,13\right\}\cup \left\{5^3,7\right\}$
Therefore, the required number of ways $=4+3=7$.