Problem:
Let S be the set of all positive integer divisors of 100,000. How many numbers are the product of two distinct elements of S?
Answer Choices:
A. 98
B. 100
C. 117
D. 119
E. 121
Solution:
Note that 100,000=25⋅55. This implies that for a number to be a product of two elements in S it must be of the form 2a⋅5b with 0≤a≤10 and 0≤b≤10. The corresponding product for the remainder of this solution will be denoted (a,b). Note that the pairs (0,0),(0,10),(10,0), and (10,10) cannot be obtained as the product of two distinct elements of S; these products can be obtained only as 1⋅1=1,55⋅55=510,25⋅25=210, and 105⋅105=1010, respectively. This gives at most 11⋅11−4=(C)117 possible products. To see that all these pairs can be achieved, consider four cases:
If 0≤a≤5 and 0≤b≤5, other than (0,0), then (a,b) can be achieved with the divisors 1 and 2a⋅5b.
If 6≤a≤10 and 0≤b≤5, other than (10,0), then (a,b) can be achieved with the divisors 25 and 2a−5⋅5b.
If 0≤a≤5 and 6≤b≤10, other than (0,10), then (a,b) can be achieved with the divisors 55 and 2a⋅5b−5.
Finally, if 6≤a≤10 and 6≤b≤10, other than (10,10), then (a,b) can be achieved with the divisors 25⋅55 and 2a−5⋅5b−5.
The problems on this page are the property of the MAA's American Mathematics Competitions