Maths Olympiad Prep

Library / /19 of 20

Number theory Difficulty 5.7 AIME, harder Prove it United States

Problem:

pp is a prime number such that the period of its decimal reciprocal is 200200. That is,

1p=0.XXXX \frac{1}{p}=0 . X X X X \ldots

for some block of 200200 digits XX, but

1p0.YYYY \frac{1}{p} \neq 0 . Y Y Y Y \ldots

for all blocks YY with less than 200200 digits. Find the 101101st digit, counting from the left, of XX.

Solution

Solution:

Let XX be a block of nn digits and let a=0.Xa=0 . X \ldots Then 10na=X.X10^{n} a=X . X \ldots. Subtracting the previous two equalities gives us (10n1)a=X\left(10^{n}-1\right) a=X, i.e. a=X10n1a=\frac{X}{10^{n}-1}.

Then the condition that a=1pa=\frac{1}{p} reduces to 1p=X10n1\frac{1}{p}=\frac{X}{10^{n}-1} or pX=10n1p X=10^{n}-1. For a given pp and nn, such an XX exists if and only if pp divides 10n110^{n}-1. Thus pp divides 10200110^{200}-1 but not 10n1,1n19910^{n}-1, 1 \leq n \leq 199. Note that 10200110^{200}-1 can be factored in this way:

102001=(10100)21=(101001)(10100+1). \begin{aligned} 10^{200}-1 & =\left(10^{100}\right)^{2}-1 \\ & =\left(10^{100}-1\right)\left(10^{100}+1\right) . \end{aligned}

Since pp is prime and does not divide 10100110^{100}-1, it must divide 10100+110^{100}+1, so that 10100+1=kp10^{100}+1=k p for an integer kk and X=(101001)(10100+1)p=(101001)kX=\frac{\left(10^{100}-1\right)\left(10^{100}+1\right)}{p}=\left(10^{100}-1\right) k.

If p=2,3,5p=2,3,5, or 77, the fraction 1p\frac{1}{p} either terminates or repeats less than 200200 digits. Therefore p>10p>10 and k<10100p<1099k<\frac{10^{100}}{p}<10^{99}. Now let us calculate the 101101st digit of X=10100kkX=10^{100} k-k, i.e. the digit representing multiples of 109910^{99}. Since 10100k10^{100} k is divisible by 1010010^{100}, its 109910^{99}s digit and all later digits are 00. Since k<1099k<10^{99}, kk does not contribute a digit to the 109910^{99}s place, but it generates a borrow to this place, changing it into a 99. Thus the 101101st digit of XX is a 99.

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.