Maths Olympiad Prep

Library / /29 of 29

Number theory Difficulty 7.1 National olympiad, round 2 Prove it Silk Road Mathematics Competition

Observe that the fraction 1/7=0.1428571/7 = 0.\overline{142857} is a pure periodical decimal with period 6=716 = 7 - 1, and in one period one has 142+857=999142 + 857 = 999. For n=1,2,n = 1, 2, \dots, find a sufficient and necessary condition that the fraction 1/(2n+1)1/(2n+1) has the same properties as above and find two such fractions other than 1/71/7.

Solution

Suppose 1/(2n+1)=a˙1a2anb1b2b˙n1/(2n+1) = \dot{a}_1 a_2 \cdots a_n b_1 b_2 \cdots \dot{b}_n, ai+bi=9a_i + b_i = 9, i=1,2,,ni = 1, 2, \dots, n, and 2n2n is its period. Since
1+1102n+1104n+=111102n=102n102n1 1 + \frac{1}{10^{2n}} + \frac{1}{10^{4n}} + \dots = \frac{1}{1 - \frac{1}{10^{2n}}} = \frac{10^{2n}}{10^{2n} - 1}
we have
(1)12n+1=102n102n1(i=1nai10i+110ni=1nbi10i)=102n102n1(i=1nai10i+110ni=1n9ai10i)=102n102n1[(1110n)i=1nai10i+910ni=1n110i]=102n102n1[(1110n)i=1nai10i+910n1101110n1110]=102n10n+1(110ni=1nai10i+1102n)=i=1n10niai+110n+1 \begin{align*} (1) \quad \frac{1}{2n+1} &= \frac{10^{2n}}{10^{2n}-1} \left( \sum_{i=1}^{n} \frac{a_i}{10^i} + \frac{1}{10^n} \sum_{i=1}^{n} \frac{b_i}{10^i} \right) \\ &= \frac{10^{2n}}{10^{2n}-1} \left( \sum_{i=1}^{n} \frac{a_i}{10^i} + \frac{1}{10^n} \sum_{i=1}^{n} \frac{9-a_i}{10^i} \right) \\ &= \frac{10^{2n}}{10^{2n}-1} \left[ \left(1-\frac{1}{10^n}\right) \sum_{i=1}^{n} \frac{a_i}{10^i} + \frac{9}{10^n} \sum_{i=1}^{n} \frac{1}{10^i} \right] \\ &= \frac{10^{2n}}{10^{2n}-1} \left[ \left(1-\frac{1}{10^n}\right) \sum_{i=1}^{n} \frac{a_i}{10^i} + \frac{9}{10^n} \cdot \frac{1}{10} \cdot \frac{1-\frac{1}{10^n}}{1-\frac{1}{10}} \right] \\ &= \frac{10^{2n}}{10^n+1} \left( \frac{1}{10^n} \sum_{i=1}^{n} \frac{a_i}{10^i} + \frac{1}{10^{2n}} \right) = \frac{\sum_{i=1}^{n} 10^{n-i} a_i + 1}{10^n+1} \end{align*}
Therefore,
2n+110n+1.2n+1 \mid 10^n + 1.
By (1) and the knowledge of numbers, we guess the sufficient and necessary condition is
(2)2n+110n+1 and 2n+110i+1 for i=1,2,,n1. (2) \quad 2n+1 \mid 10^n+1 \text{ and } 2n+1 \nmid 10^i+1 \text{ for } i=1,2,\dots,n-1.
In fact, since 2n2n is the period of 1/(2n+1)1/(2n+1), we have
2n+1102n1 and 2n+110i1 for i=1,2,,n1. 2n+1 \mid 10^{2n}-1 \text{ and } 2n+1 \nmid 10^i-1 \text{ for } i=1,2,\dots,n-1.
So 2n+1(10n+1)+(10n+i1)=10n(10i+1)2n+1 \nmid (10^n+1) + (10^{n+i}-1) = 10^n(10^i+1) for i=1,2,,n1i=1,2,\dots,n-1. Namely, 2n+110i+12n+1 \nmid 10^i+1 for i=1,2,,n1i=1,2,\dots,n-1. The condition (2) is necessary.

Now we assume that 1/(2n+1)1/(2n + 1) satisfies the condition (2). Let
10n+12n+11=i=1n10niai, \frac{10^n + 1}{2n + 1} - 1 = \sum_{i=1}^{n} 10^{n-i}a_i,
where 0ai90 \le a_i \le 9, i=1,,ni = 1, \dots, n are integers. Then
12n+1=i=1n10niai+110n+1. \frac{1}{2n + 1} = \frac{\sum_{i=1}^{n} 10^{n-i}a_i + 1}{10^n + 1}.
Put bi=9aib_i = 9 - a_i. Using (1) we have
12n+1=a˙1a2anb1b2b˙n. \frac{1}{2n + 1} = \dot{a}_1 a_2 \cdots a_n b_1 b_2 \cdots \dot{b}_n.
For 1in1 \le i \le n, because
(10n+1)+(10i1)=10i(10ni+1), (10^n + 1) + (10^i - 1) = 10^i(10^{n-i} + 1),
so 2n+110i12n + 1 \nmid 10^i - 1.
For n<i<2nn < i < 2n, because
(10n+1)+(10i1)=10n(10in+1), (10^n + 1) + (10^i - 1) = 10^n(10^{i-n} + 1),
we also have 2n+110i12n + 1 \nmid 10^i - 1.
Therefore the period of 1/(2n+1)1/(2n + 1) is 2n2n. That is, the condition (2) is sufficient.
By the condition (2), if 1/(2n+1)1/(2n + 1) is a fraction we look for, then 2n+12n + 1 does not have factors 3 and 5. So the possible values of 1/(2n+1)1/(2n + 1) are 11, 13, 17, 19, 23, .... Since 11,13103+1=100111, 13 \nmid 10^3 + 1 = 1001, 11 and 13 do not satisfy the condition. Consider 17=2×8+117 = 2 \times 8 + 1. We have
108+1=(17×42)4=24+1=0(mod17). 10^8 + 1 = (17 \times 4 - 2)^4 = 2^4 + 1 = 0 \pmod{17}.
For i=1,2,3,4i = 1, 2, 3, 4 it is obvious that 1710i+117 \nmid 10^i + 1. For i=5,6,7i = 5, 6, 7, since (108+1)(10i+1)=10i(108i1)(10^8 + 1) - (10^i + 1) = 10^i(10^{8-i} - 1), it is obvious too that 1710i+117 \nmid 10^i + 1. Therefore, 1/171/17 is a fraction we need.
Similarly, consider 19=2×9+119 = 2 \times 9 + 1.
109+1=(53×197)3+1=342=0(mod19). 10^9 + 1 = (53 \times 19 - 7)^3 + 1 = -342 = 0 \pmod{19}.
It is easy to check that 1910i+119 \nmid 10^i + 1 for 1i<91 \le i < 9. So 1/191/19 is another fraction we want to seek.

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 and solution reproduced as published; topic and difficulty added by this site.