Problem:
Let S be the set of all rational numbers that can be expressed as a repeating decimal in the form 0.abcd, where at least one of the digits a,b,c, or d is nonzero. Let N be the number of distinct numerators obtained when numbers in S are written as fractions in lowest terms. For example, both 4 and 410 are counted among the distinct numerators for numbers in S because 0.3636=114β and 0.1230=3333410β. Find the remainder when N is divided by 1000.
Solution:
Answer (392):
The repeating decimal of the form 0.abcd is equal to the fraction 9999abcdβ. Because 9999=32β
11β
101, the fraction 9999kβ written in lowest terms will have a factor of 3 in its numerator if and only if k is divisible by 33, will have a factor of 11 in its numerator if and only if k is divisible by 112, and will have a factor of 101 in its numerator if and only if k is divisible by 1012. Thus there are five cases for possible numerators for such a fraction in lowest terms.
- The fraction 9999kβ is in lowest terms if k is relatively prime to 9999 . The number of positive integers less than 10,000 relatively prime to 9999 is given by the Euler Totient Function to be
Ο(9999)=9999(1β31β)(1β111β)(1β1011β)=6000
If k is not divisible by any of 33,112 or 1012, the fraction 9999kβ, when reduced, will have a numerator relatively prime to 9999 , all of which have already been counted.
- Because 999933kβ=11β
1013kβ, the numerator can be any number of the form 3k, where kβ€β279999ββ=370 and k is relatively prime to 11 and 101 . There are
β11370ββ+β101370ββββ11β
101370ββ=33+3β0=36
positive integers less than or equal to 370 that are multiples of 11 or 101 . Thus there are 370β36=334 numerators that are relatively prime to 11 and 101 .
- Because 9999112kβ=32β
10111kβ, the numerator can be any number of the form 11k, where kβ€β1219999ββ=82 and k is relatively prime to 3 and 101 . There are
β382ββ+β10182ββββ3β
10182ββ=27+0β0=27
positive integers less than or equal to 82 that are multiples of 3 or 101 . Thus there are 82β27=55 numerators that are relatively prime to 3 and 101 .
- Because 999933β
112kβ=10133kβ, the numerator can be any number of the form 33k, where kβ€β27β
1219999ββ=3 and k is relatively prime to 101 . There are 3 such numerators.
- Because 1012>9999, there are no numerators that are multiples of 101 .
Therefore there are 6000+334+55+3=6392 possible numerators. The requested remainder is 392 .
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions