Problem:
Let be the set of positive integer divisors of . Three numbers are chosen independently and at random with replacement from the set and labeled , and in the order they are chosen. The probability that both divides and divides is , where and are relatively prime positive integers. Find .
Solution:
The prime factorization of is . Since each number , , and is a divisor of , their prime factorizations must consist of exponents of between and and exponents of between and . Thus, determining whether reduces to analyzing the exponents of and separately and checking whether the corresponding exponent triples are in nondecreasing order. The problem is therefore equivalent to choosing three exponents independently from each range and computing the probability that the selected triples are nondecreasing in each case.
In general, given a nonnegative integer , the number of integer triples such that is equal to the number of strictly increasing triples such that . This transformation maps the nondecreasing triple to a strictly increasing one by shifting the second and third elements, effectively reducing the problem to a combinatorics question with distinct elements bounded above by .
There are ways to choose , and , so the probability that the integers are chosen in order is
Thus the probability that three chosen divisors of satisfy the divisibility requirement is
The requested numerator is .
The problems on this page are the property of the MAA's American Mathematics Competitions