Kvant Math Problem 206

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m21s
Source on kvant.digital

Problem

An infinite sequence of digits is given. Prove that for any natural number $n$, coprime with 10, one can find in the sequence a block of consecutive digits such that the number formed by these digits is divisible by $n$.

V. A. Ufnarovsky

Exploration

Let the digits of the infinite sequence be $a_1,a_2,a_3,\dots$, where each $a_i \in {0,1,\dots,9}$. A block of consecutive digits from position $i$ to $j$ represents the number

$$N_{i,j} = a_i 10^{j-i} + a_{i+1} 10^{j-i-1} + \cdots + a_j.$$

The goal is to show that for every natural number $n$ with $\gcd(n,10)=1$, there exist $i \le j$ such that $N_{i,j} \equiv 0 \pmod n$.

A direct attempt using ordinary prefix sums fails because the block expression is not a simple difference of prefixes; the powers of $10$ depend on the length of the block. The key obstruction is that concatenation is not additive in a fixed modulus unless we compensate for shifting.

Since $\gcd(n,10)=1$, the residue class of $10$ modulo $n$ is invertible, which suggests introducing modular inverses of powers of $10$. The idea is to normalize each prefix number by removing the positional weight of digits.

Define prefix numbers

$$B_k = a_1 10^{k-1} + a_2 10^{k-2} + \cdots + a_k.$$

Then a block $N_{i,j}$ can be expressed using $B_j$ and $B_{i-1}$, but with a scaling factor involving $10^{j-i+1}$. The invertibility of $10$ modulo $n$ suggests that multiplying by $10^{-k}$ modulo $n$ might convert this into a telescoping structure.

The crucial step is to find a sequence of residues that converts digit concatenation into simple differences.

Problem Understanding

This is a Type A problem: we must show that for every natural number $n$ coprime with $10$, every infinite digit sequence contains a consecutive block whose numerical value is divisible by $n$.

The core difficulty is that the number represented by a block is not linear in the digits due to positional weights. The key idea should exploit the fact that $10$ is invertible modulo $n$, allowing us to normalize shifts in digit positions so that concatenation becomes compatible with modular subtraction.

We aim to construct a sequence of residues taking only finitely many values, so that two equal values produce a zero residue block.

The expected outcome is

$$\boxed{\text{every such sequence contains a block divisible by } n}.$$

Proof Architecture

Define prefix values $B_k = \sum_{i=1}^k a_i 10^{k-i}$.

Define normalized residues $C_k \equiv B_k \cdot 10^{-k} \pmod n$, where $10^{-1}$ exists modulo $n$ because $\gcd(n,10)=1$.

Prove that $C_j - C_{i-1} \equiv 0 \pmod n$ if and only if the block $a_i \dots a_j$ forms a number divisible by $n$.

Apply the pigeonhole principle to the sequence $C_0,C_1,\dots$ in $\mathbb{Z}/n\mathbb{Z}$ to obtain indices $i<j$ with equal residues.

The hardest point is verifying the equivalence between block divisibility and equality of normalized prefix residues.

Solution

Let $a_1,a_2,a_3,\dots$ be the given infinite sequence of digits. For each $k \ge 1$, define the prefix number

$$B_k = \sum_{t=1}^k a_t 10^{k-t},$$

and set $B_0=0$.

Since $\gcd(n,10)=1$, there exists an integer $u$ such that $10u \equiv 1 \pmod n$. For each integer $k \ge 0$, define $10^{-k}$ as $u^k \pmod n$.

Define

$$C_k \equiv B_k \cdot 10^{-k} \pmod n.$$

Fix indices $0 \le i \le j$. We express $B_j$ in terms of $B_{i-1}$:

$$B_j = B_{i-1} \cdot 10^{j-i+1} + \sum_{t=i}^j a_t 10^{j-t}.$$

Multiplying both sides by $10^{-j}$ in $\mathbb{Z}/n\mathbb{Z}$ gives

$$B_j 10^{-j} \equiv B_{i-1} 10^{-(i-1)} + \sum_{t=i}^j a_t 10^{-t}.$$

Hence

$$C_j \equiv C_{i-1} + \sum_{t=i}^j a_t 10^{-t} \pmod n.$$

Multiplying the last congruence by $10^j$ yields

$$C_j 10^j - C_{i-1} 10^j \equiv \sum_{t=i}^j a_t 10^{j-t} \pmod n.$$

The right-hand side is exactly the number $N_{i,j}$. Therefore

$$N_{i,j} \equiv 0 \pmod n \quad \Longleftrightarrow \quad C_j 10^j \equiv C_{i-1} 10^j \pmod n.$$

Since $10^j$ is invertible modulo $n$, this is equivalent to

$$C_j \equiv C_{i-1} \pmod n.$$

Thus a block $a_i \dots a_j$ yields a multiple of $n$ exactly when two values among $C_0,C_1,C_2,\dots$ coincide.

The residues $C_k$ lie in a set of size $n$, while the infinite sequence $(C_k){k \ge 0}$ contains infinitely many terms. By the pigeonhole principle, there exist indices $0 \le i < j$ such that $C_i \equiv C_j \pmod n$. The corresponding block $a{i+1}\dots a_j$ satisfies $N_{i+1,j} \equiv 0 \pmod n$.

This completes the proof. ∎

Verification of Key Steps

The most delicate point is the equivalence between block divisibility and equality of normalized residues. The construction relies on the identity

$$B_j = B_{i-1} 10^{j-i+1} + \sum_{t=i}^j a_t 10^{j-t},$$

which follows directly by splitting the prefix sum at position $i-1$ and factoring powers of $10$.

The second subtle point is the legitimacy of dividing by powers of $10$ modulo $n$. This is valid because $\gcd(10,n)=1$, so $10$ is invertible in the residue ring, and hence all powers $10^k$ are invertible as well.

Finally, the pigeonhole argument depends only on the finiteness of residue classes modulo $n$, not on any structure of the digits, ensuring that repetition of $C_k$ is unavoidable.

Alternative Approaches

One alternative approach avoids explicit normalization and instead considers pairs $(B_k,10^k)$ as elements of a finite module over $\mathbb{Z}/n\mathbb{Z}$, then applies a linear dependence argument in the semidirect structure induced by digit concatenation. This method encodes blocks as differences in an affine action.

Another approach uses automata theory: the set of residues of prefixes forms a finite deterministic automaton under digit input, and any infinite input word induces a loop, which corresponds to a zero-weight cycle producing a divisible block. The normalization method above is more direct and avoids formal machinery beyond modular inverses and pigeonhole principle.