Relatively prime factors of $24500$

283 Views Asked by At

Let $N=24500$, then find the number of ways by which $N$ can be resolved into two coprime factors?

My tries:

$N=24500=2^2\cdot 5^3\cdot 7^2$, for co prime no those two factors of $24500$ should share something in common, so the two factors should be such that either one of the two should use all of $2's,5's,7's$, hence picking up any two from $2^2\cdot 5^3\cdot 7^2\ \ ,\ \# ={3\choose {2}}=3$, then multiplying them together to get new number, for example $2^2\cdot 7^2=196$, then we are left with $5^3$, hence one such possible resolution should be $196\cdot 5^3$. So, ${3\choose {2}}=3$ should count all answer, but book says answer should be $4$.

Please help.

2

There are 2 best solutions below

0
On BEST ANSWER

Your idea was correct, namely that we separate the prime powers as different units : $2^2,5^3,7^2$, and then combine some set of them to form one of the numbers, leaving the remaining to form the other number.

Now, if we write down these components as a set, and try to understand what "set-counting" argument leads to the situation. Consider this set that we have: $$ \{2^2,5^3,7^2\} $$ Choose any subset of this set: I'll color those chosen in that subset in red, and those not chosen in blue: $$ \{\color{blue}{2^2},\color{red}{5^3},\color{red}{7^2}\} $$ Now, we multiply the elements chosen and not chosen in the subset separately, and write down the answers: $\color{blue}{2^2 = 4} ,\color{red}{5^3 \times 7^2 = 6125}$.

This gives us a pair : $\{4,6125\}$ of coprime numbers corresponding to this subset.

Similarly, you can show that every subset of $\{2^2,5^3,7^2\}$, including the empty one, corresponds to a break up of $2^2 \times 5^3 \times 7^2$ into two coprime factors.

However, there's a catch : the following subsets below would give the same pair of numbers : $$ \{\color{blue}{2^2},\color{red}{5^3,7^2}\} \quad \{\color{red}{2^2},\color{blue}{5^3,7^2}\} $$

I think you see the relation between the subsets above. The second subset is precisely the complement of the first subset.(These will give rise to the same pair of numbers. Furthermore, if two subsets are not related in this fashion, they will definitely give rise to a different pair of numbers, as you can see for yourself or prove).

Therefore, now, the number of possible decompositions of $24500$ into coprime factors, is the number of subsets of $\{2^2,5^3,7^2\}$ divided by two. What is this? The number of subsets of a set of size $n$ is just $2^n$. Division by two is multiplication by $2^{-1}$. Hence, the answer is written as $2^{3-1} = 4$, whence I hope you understand how your answer was written.

ADDENDUM : Using a similar logic, if a number $n = \prod_{i=1}^m p_i^{\alpha_i}$, where $p_i$ are distinct primes and $\alpha_i \geq 1$, then $n$ has $2^{m-1}$ decompositions into a pair of coprime factors.

3
On

For integer $a,b,c>0$

$$2^a\cdot5^b\cdot7^c=(1\cdot2^a)(1\cdot5^b)(1\cdot7^c)$$

$=((1\cdot2^a5^b)$ or $(2^a\cdot5^b))(1\cdot7^c)$

$=(1\cdot2^a5^b7^c)$ or $(7^c\cdot2^a5^b)$ or $(2^a7^c,5^b)$ or $(2^a,5^b7^c)$