Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
add comment

1 Answer

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$.

share|improve this answer
1  
The question was about sets, not triples, so I think the result should be $276/6=46$. This can also be obtained more directly: If all three primes are present, they can be distributed over all three factors in one way or over two factors in three ways, for a total of $4\cdot(4\cdot2\cdot1)$ possibilities. If only two primes are present, they have to be distributed over two factors, and the counts are $4\cdot2$, $4\cdot1$ and $2\cdot1$, respectively, for a total of $32+8+4+2=46$. –  joriki Jul 16 '12 at 7:00
    
If we write the given number as $D_1 D_2 D_3$ where $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}$ . So, the problem reduces to finding number of unique possible combinations of $a_i, b_j, c_k $s such that $\sum a_i=4$ and so on. The uniqueness can be ensured by making $a_i ≥ a_j$ where i>j and so on. –  lab bhattacharjee Jul 16 '12 at 11:31
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. –  Zev Chonoles Jul 16 '12 at 11:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.