Problem:
Let and be the unique relatively prime positive integers such that
Let denote the least common multiple of the numbers . For how many integers with is
Answer Choices:
A.
B.
C.
D.
E.
Solution:
In assessing the denominator of the sum of rational numbers, the following principle is useful. Suppose that
where for . Let be a prime number, and suppose that is the greatest power of that divides , that is the greatest power of that divides , and that . Then is the greatest power of that divides . To see why this is true, let denote the greatest power of that divides . Multiply both sides of the displayed equation by . Then the resulting left-hand side is a rational number with no in the denominator. The power of in the factorization of the right-hand side is . Hence . Next, instead of multiplying the above equation by , now multiply by . Then occurs to the first power in the denominator of the first term, does not occur at all in the second denominator, and on the right-hand side the contribution of to the denominator is . Thus . From these inequalities it follows that .
Let
It is useful to note that
The greatest power of 2 that divides is , where is the greatest integer such that . This is the same as the greatest power of 2 that divides . For there is only one summand in with a 3 in the denominator. For , there are two such terms; they contribute
Hence for these , the power of 3 in the denominator is less than the power of 3 in . For there is only one term in whose denominator has a factor . For there are two, and they contribute . Thus the power of 3 in the denominator is less than the power of 3 in for these .\
For , the summands that have a 5 in the denominator contribute one of
None of , or is divisible by 5 , but , so 5 does not appear in the denominator of for . For , the contribution of 7 to the denominator of is one of
Because 7 does not divide any of , or , it follows that for , as in . The contributions of 11 to the denominator of is or , so for . The primes 13,17 , and 19 occur in at most one denominator in for , and therefore occur with the same multiplicity in and in this range.
Thus for , the inequality holds if and only if , or 22 , a total of values.
Note: The quantity is known as a harmonic number.
The problems on this page are the property of the MAA's American Mathematics Competitions