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:
We have that
0.abcd=9999abcdβ
and factoring , we have that 9999=9Γ11Γ101
Then we need to find the number of positive integers less than 10000 that can meet the requirement. Let's write the number as reduced
9999abcdβ=yxβ
Case 1: gcd(9999,x)=1.
Notice that any fraction that x is relatively prime to 9999 will just reduce to 9999xβ and the number of solutions is
Ο(9999)=9999Γ(1β31β)Γ(1β111β)Γ(1β1011β)=6000
Case 2: The first factor that can may divide x is 3. In this case suppose 3β£x but x is not a multiple of 11 or 101. We'd need abcd to have an extra factor of 9 beyond this factor of 3, in order for the factor of 9's to cancel from the numerator and denominator, so we could write abcd=9x
This would bound 9xβ€9999βxβ€1111 and we need x to be a multiple of 3 not divisible by 11 or 101 and since
lcm(11,101)=1111, we can find the numbers that aren't divisible by 11 and 101 separately.
The total number of possible values is β31011ββ=370.
The first set of bad cases is multiples of 11, so we have to subtract β3β
111011ββ=30
The next set of bad cases is multiples of 101, so we have to subtract β3β
1011111ββ=3.
So the total of this case is
370β33β3=334
Case 3: In this case, we'd have that 11β£x but x is not a multiple of 3 or 101. The idea for this case is the exact same, in particular that we'd need abcd=11x, and then that bounds xβ€119999β=909
We do similar exclusion as above to get
β11909ββββ3β
11909ββββ11β
101909ββ=55
Case 4: 101β£x. In this case, we'd need abcd=101x and there'd be no valid solutions.
Case 5: Lastly, we'd have that both 3β£x and 11β£x. Then the least value of abcd is 99x
and solving this we'd have
β33101ββββ33β
101101β=3β
Adding this up, we get
6000+334+55+3β‘6392β‘392βmod1000
The problems on this page are the property of the MAA's American Mathematics Competitions