Maths Olympiad Prep

Library / /73 of 348

Number theory Difficulty 4.7 AIME Find the answer

For how many positive integers n100n \leq 100 is it true that 10n10 n has exactly three times as many positive divisors as nn has?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let n=2a5bcn=2^{a} 5^{b} c, where 2,5c2,5 \nmid c. Then, the ratio of the number of divisors of 10n10 n to the number of divisors of nn is a+2a+1b+2b+1=3\frac{a+2}{a+1} \frac{b+2}{b+1}=3. Solving for bb, we find that b=1a2a+1b=\frac{1-a}{2 a+1}. This forces (a,b)=(0,1),(1,0)(a, b)=(0,1),(1,0). Therefore, the answers are of the form 2k2 k and 5k5 k whenever gcd(k,10)=1\operatorname{gcd}(k, 10)=1. There are 50 positive numbers of the form 2k2 k and 20 positive numbers of the form 5k5 k less than or equal to 100. Of those 70 numbers, only 1245\frac{1}{2} \cdot \frac{4}{5} have kk relatively prime to 10, so the answer is 701245=2870 \cdot \frac{1}{2} \cdot \frac{4}{5}=28.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.