Maths Olympiad Prep

Library / /61 of 136

Number theory Difficulty 7.8 National Olympiad, round 2 Prove it Hong Kong

Let nn be a positive integer. When n567\frac{n}{567} is expressed as a decimal, it is a recurring decimal with smallest period kk. Find the sum of all possible values of kk. (Note: We say that kk is a period of a recurring decimal if starting from some place the digits of the decimal repeat every kk digits. For instance, 0.123453453450.12345345345\dots has smallest period 3 while 0.1428571425871425870.142857142587142587\dots has smallest period 6.)

Solution

The answer is 3737.

We first prove the following result.
Claim. Consider a positive rational number ab\frac{a}{b} where (10a,b)=1(10a, b) = 1. The smallest period of this number when expressed as a decimal number is the order of 1010 modulo bb.
Proof. Note that ab\frac{a}{b} has period kk if and only if the tail part of 10kab10^k \cdot \frac{a}{b} is the same as that of ab\frac{a}{b}. This holds if and only if (10k1)ab(10^k - 1) \cdot \frac{a}{b} is a terminating decimal, i.e. 10m(10k1)abZ10^m(10^k - 1) \frac{a}{b} \in \mathbb{Z} for some nonnegative integer mm. Equivalently, this means
b10m(10k1)a. b \mid 10^m(10^k - 1)a.
As (10a,b)=1(10a, b) = 1, this is the same as b10k1b \mid 10^k - 1. By definition, the smallest positive integer kk for which this holds is the order of 1010 modulo bb. \square

Now, when nn runs through all positive integers, the denominator of n567\frac{n}{567} in the lowest term can be any positive divisor of 567=34×7567 = 3^4 \times 7. Let dbd_b be the order of 1010 modulo bb. By the claim, it suffices to find dbd_b for each positive divisor bb of 567567.
* Since 101(mod9)10 \equiv 1 \pmod{9}, we have d1=d3=d9=1d_1 = d_3 = d_9 = 1.
* Since 10≢1(mod27)10 \not\equiv 1 \pmod{27} and 103=10001(mod27)10^3 = 1000 \equiv 1 \pmod{27}, we have d27=3d_{27} = 3.
* Since 103=1000≢1(mod81)10^3 = 1000 \not\equiv 1 \pmod{81} and
109=10003=(27×37+1)31(mod81) 10^9 = 1000^3 = (27 \times 37 + 1)^3 \equiv 1 \pmod{81}
by the binomial theorem, we have d81=9d_{81} = 9.
* Since φ(7)=6\varphi(7) = 6 and 102,103≢1(mod7)10^2, 10^3 \not\equiv 1 \pmod{7}, we have d7=6d_7 = 6.
* For b=3s7b = 3^s7 where s=1,2,3,4s = 1, 2, 3, 4, we have db=[d3s,d7]d_b = [d_{3^s}, d_7]. Therefore, we easily deduce d21=d63=d189=6d_{21} = d_{63} = d_{189} = 6, d567=18d_{567} = 18.
It follows that the answer is 1+3+6+9+18=371 + 3 + 6 + 9 + 18 = 37.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.