0
$\begingroup$

What is the total number of sets of $3$ distinct factors of the number $X = 26 × 34 × 52$ that can be made such that the factors in each set has a $\gcd$ of $1$ w.r.t. every other factor in that set?

I'm getting $22$, but the options are, $104$, $360$, $380$, or $236$.

1 Answers 1

2

I'm getting $276$, but it's late where I am and I'm probably making a mistake. However, I'll post my thoughts in case someone can see where my error is and how to fix it.

EDIT: As Joriki points out below, the original question was asking about sets of factors, not triples, so we should divide by the number of ways of rearranging a triple, namely 6, producing a final answer of $276/6=46$.


We have that $X=(2\times 13)\times(2\times 17)\times(4\times 13)=2^4\times 13^2\times 17$ Therefore, the factors of $X$ are precisely the integers of the form $2^a\times 13^b\times 17^c$ where $0\leq a\leq 4$, $0\leq b\leq 2$, and $0\leq c\leq 1$. In other words, a factor is uniquely specified by a triple in the set $A\times B\times C=\{0,1,2,3,4\}\times\{0,1,2\}\times\{0,1\}.$ A triple of factors is specified uniquely by an element of the set $A^3\times B^3\times C^3$.

Three factors $D_1=2^{a_1}13^{b_1}17^{c_1}$, $D_2=2^{a_2}13^{b_2}17^{c_2}$, and $D_3=2^{a_3}13^{b_3}17^{c_3}$ of $X$ are coprime precisely when at most one $a_i>0$, at most one $b_i>0$, and at most one $c_i>0$. The condition that the factors be distinct rules out $D_i=D_j=1$, i.e. $a_i=a_j=b_i=b_j=c_i=c_j=0$ for some distinct $i,j\in\{1,2,3\}$.

We want to throw out the triples of exponents $(a_1,a_2,a_3)$ from $A^3$ for which there is more than one $a_i>0$. There are $13$ remaining triples of exponents from $A^3$, namely $(a_1,0,0)$ for some $a_1\in A$, $(0,a_2,0)$ for some $a_2\in A$, $(0,0,a_3)$ for some $a_3\in A$ (this counts the triple $(0,0,0)$ three times, hence $13=15-2$).

By the same reasoning, we obtain $7$ remaining triples of exponents in $B^3$, and $4$ triples of exponents in $C^3$. This brings us down to $13\times 7\times 4=364$ possible triples of factors $(D_1,D_2,D_3)$.

Now we consider the condition that the factors be distinct. We have already thrown out the triples of exponents that would be necessary to having the same non-one factor occur twice, so the only possibility is that the factor $1$ is repeated. Either there are exactly two $D_i,D_j=1$, or all three $D_1=D_2=D_3=1$.

Consider the former case; i.e. suppose that $D_i=D_j=1$, so that $a_i=a_j=b_i=b_j=c_i=c_j=0$. The number of ways of choosing $(a_k,b_k,c_k)\neq(0,0,0)$ for the remaining $k\neq i,j$ is $(5\times 3\times 2)-1=29$. There are three possible pairs of distinct $i,j\in\{1,2,3\}$, so in total, the number of triples we need to throw out (that correspond to having exactly two of the factors equal to $1$) is $3\times 29=87$, leaving us with $277$.

Lastly, there is exactly one way of getting $D_1=D_2=D_3=1$, namely $a_i=b_i=c_i=0$ for all $i\in\{1,2,3\}$, so we throw out one more for $276$.

  • 1
    @labbhattacharjee: I don't see any requirement that the factors of $X$ in one of these sets also must multiply to $X$. For example, the set $\{2,13,17\}$ should be a perfectly fine set of factors, if I understand the problem correctly.2012-07-16