Kvant Math Problem 1280

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m42s
Source on kvant.digital

Problem

Prove that in the repeating part of the decimal fraction $\dfrac{1}{3^{100}}$ there will appear

at least 20 identical digits in a row;
the digit sequence 123456789.

A. Korobov

Exploration

The decimal expansion of $\dfrac1{3^{100}}$ is purely periodic after a finite preperiod, because $3^{100}$ is coprime to $10$. The period length is the multiplicative order of $10$ modulo $3^{100}$.

To understand what digits occur, write the long division process. If at some stage the remainder is $r$, then the next digit is

$$a=\left\lfloor \frac{10r}{3^{100}}\right\rfloor,$$

and the next remainder is

$$r'=10r-a,3^{100}.$$

Since multiplication by $10$ permutes the nonzero residue classes modulo $3^{100}$, every positive integer not divisible by $3$ occurs exactly once among the remainders during a full period.

Hence a block of digits corresponds to a chain of inequalities for successive remainders.

For twenty equal digits, it is natural to ask whether there exists a remainder producing twenty consecutive zeros. If the next twenty digits are all $0$, then

$$10^k r<3^{100}\qquad (k=1,\dots,20).$$

The strongest condition is

$$10^{20}r<3^{100}.$$

There are many admissible remainders because

$$\frac{3^{100}}{10^{20}} \approx 5.15\cdot10^{27}.$$

Among them there must be numbers not divisible by $3$. Such a remainder occurs in the cycle, yielding twenty consecutive zeros.

For the block $123456789$, suppose the remainder before the block is $r$. The first digit being $1$ means

$$3^{100}\le 10r<2\cdot3^{100}.$$

After one step the new remainder is $10r-3^{100}$. Requiring the second digit to be $2$ gives

$$2\cdot3^{100}\le 10(10r-3^{100})<3\cdot3^{100},$$

which simplifies to

$$12\cdot3^{100}\le 10^2r<13\cdot3^{100}.$$

Continuing suggests the pattern

$$N_k,3^{100}\le 10^k r<(N_k+1),3^{100},$$

where $N_k=123\ldots k$.

For $k=9$,

$$123456789\cdot3^{100}\le 10^9r<123456790\cdot3^{100}.$$

The interval for $r$ has length

$$\frac{3^{100}}{10^9},$$

which is enormous, far larger than $1$. Hence it contains integers. Any integer in it produces the desired block. The only remaining issue is to ensure that such an integer is not divisible by $3$, because only then does it occur among the periodic remainders. Since the interval length exceeds $3$, it contains three consecutive integers, one of which is not divisible by $3$.

The delicate point is proving rigorously that the inequalities indeed encode the prescribed digit string.

Problem Understanding

We must show that the repeating part of the decimal expansion of

$$\frac1{3^{100}}$$

contains two specific patterns.

First, somewhere in one period there are at least $20$ consecutive identical digits.

Second, somewhere in one period the block

$$123456789$$

appears.

This is a Type B problem. The main difficulty is translating conditions on decimal digits into conditions on the remainders arising in the long division algorithm, and then proving that suitable remainders actually occur in the periodic cycle.

Proof Architecture

The first lemma states that during one full period of the decimal expansion of $1/3^{100}$, the remainders are precisely the positive integers less than $3^{100}$ that are not divisible by $3$.

Its proof uses the fact that multiplication by $10$ is a permutation modulo $3^{100}$.

The second lemma states that if a remainder $r$ satisfies

$$10^m r<3^{100},$$

then the next $m$ digits of the decimal expansion are all $0$.

Its proof follows directly from the long division inequalities.

The third lemma states that if

$$N_k,3^{100}\le 10^k r<(N_k+1),3^{100},$$

where $N_k=123\ldots k$, then the first $k$ digits generated from remainder $r$ are exactly $1,2,\dots,k$.

Its proof is an induction on $k$.

The hardest point is the third lemma, because one must verify carefully that the inequalities propagate correctly through the division process.

Solution

Let

$$M=3^{100}.$$

Consider the decimal expansion of $1/M$ obtained by long division.

If $r_n$ is the remainder before producing the $n$-th digit, then

$$10r_n=a_nM+r_{n+1}, \qquad 0\le r_{n+1}<M,$$

where $a_n$ is the $n$-th decimal digit.

Since $(10,M)=1$, multiplication by $10$ is a permutation of the residue classes modulo $M$. Therefore, during one complete period, the remainders run through all nonzero residue classes modulo $M$ that are relatively prime to $M$. Since $M=3^{100}$, these are exactly the integers

$$1\le r<M,\qquad 3\nmid r.$$

Thus every such remainder occurs somewhere in the repeating part.

We first prove part 1.

Suppose a remainder $r$ satisfies

$$10^{20}r<M.$$

Then for every $k=1,\dots,20$,

$$10^k r<M.$$

The first digit produced from $r$ is

$$\left\lfloor \frac{10r}{M}\right\rfloor =0.$$

The next remainder is $10r$, so the second digit is

$$\left\lfloor \frac{10^2r}{M}\right\rfloor =0.$$

Continuing in the same way, the first twenty digits produced from $r$ are all equal to $0$.

It remains to show that such an $r$ occurs among the periodic remainders. The interval

$$1\le r<\frac{M}{10^{20}}$$

contains

$$\frac{M}{10^{20}}-1$$

positive integers. Since

$$3^{100}>10^{20},$$

this interval is nonempty. In fact,

$$\frac{3^{100}}{10^{20}}>3,$$

so it contains at least three consecutive integers, one of which is not divisible by $3$. Choose such an integer $r$.

This remainder occurs in the periodic cycle, and from it the next twenty digits are

$$00000000000000000000.$$

Hence the repeating part contains at least twenty identical digits in a row.

Now we prove part 2.

For $k=1,\dots,9$, let

$$N_k=123\ldots k.$$

Thus

$$N_1=1,\quad N_2=12,\quad \dots,\quad N_9=123456789.$$

Choose an integer $r$ satisfying

$$N_9M\le 10^9r<(N_9+1)M.$$

The interval

$$\left[\frac{N_9M}{10^9},\frac{(N_9+1)M}{10^9}\right)$$

has length

$$\frac{M}{10^9}.$$

Since

$$\frac{3^{100}}{10^9}>3,$$

it contains at least three consecutive integers. Choose one that is not divisible by $3$. Such an $r$ occurs among the periodic remainders.

We claim that the next nine digits generated from $r$ are

$$1,2,3,4,5,6,7,8,9.$$

Define

$$r_0=r.$$

For $k=1,\dots,9$, let

$$r_k=10^k r-N_kM.$$

From the choice of $r$,

$$0\le r_9<M.$$

We prove by descending induction on $k$ that

$$N_kM\le 10^k r<(N_k+1)M \qquad (k=1,\dots,9).$$

The statement for $k=9$ is exactly the choice of $r$.

Assume

$$N_kM\le 10^k r<(N_k+1)M.$$

Since

$$N_k=10N_{k-1}+k,$$

dividing by $10$ gives

$$\left(N_{k-1}+\frac{k}{10}\right)M \le 10^{k-1}r < \left(N_{k-1}+\frac{k+1}{10}\right)M.$$

Because $k\le 9$,

$$\frac{k}{10}<1,\qquad \frac{k+1}{10}\le1.$$

Hence

$$N_{k-1}M\le 10^{k-1}r<(N_{k-1}+1)M.$$

The induction is complete.

Therefore, for every $k=1,\dots,9$,

$$N_kM\le 10^k r<(N_k+1)M.$$

We now determine the digits. For $k=1$,

$$M\le 10r<2M,$$

so the first digit is $1$.

Assume the first $k-1$ digits are $1,2,\dots,k-1$. Then the remainder after these digits is

$$r_{k-1}=10^{k-1}r-N_{k-1}M.$$

Multiplying by $10$,

$$10r_{k-1}=10^k r-10N_{k-1}M.$$

Using

$$N_k=10N_{k-1}+k$$

and

$$N_kM\le 10^k r<(N_k+1)M,$$

we obtain

$$kM\le 10r_{k-1}<(k+1)M.$$

Hence the next digit is exactly $k$.

By induction, the first nine digits produced from $r$ are

$$123456789.$$

Since the chosen remainder occurs in the periodic cycle, the repeating part of the decimal expansion of $1/3^{100}$ contains the block $123456789$.

This completes the proof.

∎

Verification of Key Steps

For the block of twenty zeros, the crucial fact is that the remainder after each zero digit is multiplied by $10$. Starting from

$$10^{20}r<M,$$

we obtain

$$10^k r<M$$

for every $k\le20$.

The $k$-th digit is

$$\left\lfloor \frac{10^k r}{M}\right\rfloor,$$

which equals $0$. A careless argument might assume that one inequality is enough, without checking that every intermediate digit is controlled.

For the block $123456789$, the essential identity is

$$N_k=10N_{k-1}+k.$$

From

$$N_kM\le10^k r<(N_k+1)M$$

one gets

$$kM\le10r_{k-1}<(k+1)M,$$

where

$$r_{k-1}=10^{k-1}r-N_{k-1}M.$$

This is exactly the condition that the next digit equals $k$. Omitting the explicit computation of $10r_{k-1}$ would leave the central step unproved.

The existence of a suitable remainder requires more than showing that the interval is nonempty. The periodic remainders are precisely the integers not divisible by $3$. Since the interval length is

$$\frac{3^{100}}{10^9}>3,$$

it contains at least three consecutive integers, guaranteeing that one of them is not divisible by $3$.

Alternative Approaches

Instead of working directly with remainders, one may use the cyclic sequence

$$10^n \pmod{3^{100}}.$$

Every nonzero residue class modulo $3^{100}$ that is not divisible by $3$ appears as some power of $10$. The decimal digits are determined by the positions of these residues inside intervals of the form

$$[dM,(d+1)M).$$

The desired digit patterns correspond to finding powers of $10$ whose residues lie in suitable nested intervals. This leads to the same inequalities but expressed entirely in modular language.

Another approach is to view the decimal expansion as the orbit of the map

$$x\mapsto {10x}$$

on fractions with denominator $3^{100}$. The desired digit strings correspond to cylinder sets in the symbolic dynamics of this map. Because the orbit visits every admissible state, it suffices to show that the corresponding cylinder sets contain admissible states. The interval computations above provide exactly that verification.