AMC 10 Daily Practice Round 3

Suppose that and are positive integers with . We determine the number of triples with this property. (We are temporarily ignoring the size ordering condition in the original question.) Since the product has two factors of , then and have a total of two factors of . There are ways in which this can happen: both factors in , both factors in , both in , one each in and , one each in and , and one each in and . Similarly, there are ways of distributing each of the other squares of prime factors. Since includes exactly squares of prime factors and each can be distributed in ways, there are ways of building triples using the prime factors, and so there are triples with the required product.

Next, we include the condition that no pair of and should be equal. (We note that and cannot all be equal, since their product is not a perfect cube.) We count the number of triples with one pair equal, and subtract this number from . We do this by counting the number of these triples with . By symmetry, the number of triples with and with will be equal to this total. In order to have and and , for each of the squared prime factors of , either is distributed as and in each of and , or is distributed to . Thus, for each of the squared prime factors , there are ways to distribute, and so triples with and and . Similarly, there will be triples with and triples with . This means that there are triples () with the required product and with no two of equal. The original problem asked us to the find the number of triples () with the given product and with . To convert triples with no size ordering to triples with , we divide by . (Each triple corresponds to triples of distinct positive integers with no size ordering.) Therefore, the total number of triples () with the required properties is

When is divided by , the remainder is .