Maths Olympiad Prep

Library / IMO Hk TST /50 of 119

IMO Hk TST

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.12345345345…0.12345345345\dots has smallest period 3 while 0.142857142587142587…0.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 10k⋅ab10^k \cdot \frac{a}{b} is the same as that of ab\frac{a}{b}. This holds if and only if (10k−1)⋅ab(10^k - 1) \cdot \frac{a}{b} is a terminating decimal, i.e. 10m(10k−1)ab∈Z10^m(10^k - 1) \frac{a}{b} \in \mathbb{Z} for some nonnegative integer mm. Equivalently, this means
b∣10m(10k−1)a. b \mid 10^m(10^k - 1)a.
As (10a,b)=1(10a, b) = 1, this is the same as b∣10k−1b \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 10≡1(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=1000≡1(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)3≡1(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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.