1
$\begingroup$

Find the number of ordered triples $(a,b,c)$ of positive integers so that the following relations hold: $$a\times\gcd (b,c)=b\times \gcd (a,c)=c\times \gcd (a,b)=2^6 \times 3^8 \times 5^{10} $$ I just know the official answer is 2080.

I think we must consider the prime factorization of $a,b,c$ and try to find the powers of primes in each,but seems too difficult to me...

$\endgroup$
2
+50
$\begingroup$

Well first off, each of the $a,b,c$ divide $2^63^85^{10}$ so each $a,b,c$ is of the form $2^m3^k5^j$.

Let $a = 2^{m_a}3^{k_a}5^{j_a};b = 2^{m_b}3^{k_b}5^{j_b};c = 2^{m_c}3^{k_c}5^{j_c}$

$a\gcd(b,c) = 2^{m_a + \min(m_b, m_c)} 3^{k_a + \min(k_b, k_c)}5^{j_c + \min(j_b, j_c}$ etc.

So $m_a + \min(m_b, m_c) = m_b+ \min(m_a, m_c) = m_c + \min(m_a, m_b)=6$. etc.

Let's label $m_1$ to be the least of $m_a, m_b, m_c$ and $m_2$ to be the median value of of $m_a, m_b, m_c$ and $m_3$ to be the maximum of the three.

So $m_1 + m_2 = m_2 + m_1 = m_3 + m_1 = 6$ so $m_2 = m_3 = 6 - m_1$ so the possible values are $(0, 6,6), (1,5,5), (2,4,4), (3,3,3)$. For the first three there are $3$ options for whether it is $m_a, m_b$ or $m_c$ that is the least value. So there are 10 possible ways to distribute the powers of $2$ to the triplets.

I.E. the triples must be of one of these 10 forms:

$a = 3^{k_a}5^{j_a};b = 64*3^{k_b}5^{j_b};c = 64*3^{k_c}5^{j_c}$.. $a = 64*3^{k_a}5^{j_a};b = 3^{k_b}5^{j_b};c = 64*3^{k_c}5^{j_c}$..$a = 64*3^{k_a}5^{j_a};b = 64*3^{k_b}5^{j_b};c = 3^{k_c}5^{j_c}$. or

$a = 2*3^{k_a}5^{j_a};b = 32*3^{k_b}5^{j_b};c = 32*3^{k_c}5^{j_c}$.. $a = 32*3^{k_a}5^{j_a};b = 23^{k_b}5^{j_b};c = 32*3^{k_c}5^{j_c}$..$a = 32*3^{k_a}5^{j_a};b = 32*3^{k_b}5^{j_b};c = 2*3^{k_c}5^{j_c}$. or

$a = 4*3^{k_a}5^{j_a};b = 16*3^{k_b}5^{j_b};c = 16*3^{k_c}5^{j_c}$.. $a = 16*3^{k_a}5^{j_a};b = 4*3^{k_b}5^{j_b};c = 16*3^{k_c}5^{j_c}$..$a = 16*3^{k_a}5^{j_a};b = 16*3^{k_b}5^{j_b};c = 4*3^{k_c}5^{j_c}$. or

$a = 8*3^{k_a}5^{j_a};b = 8*3^{k_b}5^{j_b};c = 8*3^{k_c}5^{j_c}$

By the exact same reasoning, the powers of $3$ must be: $(0,8,8)....(3,5,5)(4,4,4)$ and there are $3*4 + 1 = 13$ ways to distribute the powers of $3$ into triplets.

And the powers of $5$ must be: $(0, 10,10) .... (4,6,6)(5,5,5)$ and there are $3*5+1 = 16$ ways to distribute the powers of $5$ into triplets.

SO there are $10*13*16 = 2080$ possible triplets.

They are $a = 2^{m_a}3^{k_a}5^{j_a};b = 2^{m_b}3^{k_b}5^{j_b};c = 2^{m_c}3^{k_c}5^{j_c}$ where

  • two of $m_a, m_b, m_c$ are equal and larger or equal to the third and the sum of all three add to $6$. (There are 10 ways to do this.)
  • two of $j_a, j_b, j_c$ are equal and larger or equal to the third and the sum of all three add to $8$. ( There are 13 ways to do this.)
  • two of $k_a, k_b, k_c$ are equal and larger or equal to the third and the sum of all three add to $10$. (There are 16 ways to do this.)
$\endgroup$
2
$\begingroup$

Hint:

Let the highest power of $2$ in $a,b,c$ be $A,B,C$

$\implies A+$min$(B,C)=B+$min$(C,A)=C+$min$(A,B)=6$

Now WLOG $A\ge B\ge C$

$\implies A+B=C+A=6\implies B=C,6=A+B\le A+A\iff A\ge3$

So, we can have four combinations $\{(3,3);(4,2);(5,1);(6,0)\}$

Similarly for the other two primes namely, $3,5$

$\endgroup$
  • $\begingroup$ What do you mean by "highest power of 2" ??!! I think it's no meaning! Every prime has a certain power in a unique factorization of a given number $\endgroup$ – Hamid Reza Ebrahimi Apr 29 '17 at 18:38
  • $\begingroup$ @fleablood Hey man,I already knew that!! I mean "highest power" in the prime factorization has no useful meaning... $\endgroup$ – Hamid Reza Ebrahimi Jun 16 '17 at 2:56
  • $\begingroup$ Sure it does. "Highest power of two that divides k" and "the power of 2 in the prime factorization of k" are two ways of saying the exact same thing. In my opinion the first is more natural and common. It certainly not "??!!" worthy. $\endgroup$ – fleablood Jun 16 '17 at 5:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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