Kvant Math Problem 34
The number
Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m02s
Source on kvant.digital
Problem
Prove that if a natural number is divisible by $10,101,010,101$, then in its decimal representation at least six digits are nonzero.
A. K. Tolpygo
Moscow Mathematical Olympiad (1970)
Exploration
The number
$$10,101,010,101$$
has a very suggestive decimal form. Computing,
$$10,101,010,101=10^{10}+10^8+10^6+10^4+10^2+1.$$
It is useful to factor it. Since
$$10^{12}-1=(10^6-1)(10^6+1),$$
and
$$10^{12}-1=(10^2-1)(10^{10}+10^8+10^6+10^4+10^2+1),$$
we get
$$10,101,010,101=\frac{10^{12}-1}{99}.$$
A direct computation gives
$$10,101,010,101=73\cdot 137\cdot 99990001.$$
The factors $73$ and $137$ are familiar because
$$1000+1=1001=7\cdot 11\cdot 13, \qquad 10^3\equiv -1 \pmod{73}, \qquad 10^3\equiv -1 \pmod{137}.$$
The statement concerns decimal representations with few nonzero digits. Any number with at most five nonzero digits can be written as
$$N=\sum_{i=1}^{5} a_i10^{n_i},$$
where $0\le a_i\le 9$ and some coefficients may be $0$.
To prove that such an $N$ cannot be divisible by $10,101,010,101$, it suffices to show that no nontrivial linear combination of at most five powers of $10$ with coefficients of absolute value at most $9$ can be divisible by this number.
Modulo $73$ and $137$, powers of $10$ have period $6$ because $10^3\equiv -1$. Hence every power is congruent to one of
$$\pm1,\ \pm10,\ \pm27$$
modulo $73$, since $10^2\equiv27\pmod{73}$.
The crucial question is whether a sum of at most five such residues, each multiplied by a digit $1,\dots,9$, can vanish modulo $73$ and modulo $137$ simultaneously. A cleaner route is to group decimal positions according to their exponents modulo $6$. Then divisibility by both $73$ and $137$ forces a certain alternating relation among six digit sums. Since there are at most five nonzero digits, at least one of these six groups is empty. The resulting relation may force all six group sums to be zero.
This is the step most likely to hide an error and must be proved carefully.
Problem Understanding
We must prove that every positive integer divisible by
$$10,101,010,101$$
contains at least six nonzero digits in its decimal expansion.
This is a Type B problem. The claim is given and must be proved.
The core difficulty is to convert divisibility by the large number
$$10,101,010,101$$
into restrictions on the distribution of decimal digits. The natural structure comes from the congruences
$$10^6\equiv1\pmod{73}, \qquad 10^6\equiv1\pmod{137},$$
which allow us to collect digits according to positions modulo $6$.
Proof Architecture
First, prove that
$$10,101,010,101=73\cdot137\cdot99990001.$$
This implies that every multiple of $10,101,010,101$ is divisible by both $73$ and $137$.
Next, for a decimal number
$$N=\sum d_n10^n,$$
define
$$S_r=\sum_{n\equiv r\ (\mathrm{mod}\ 6)} d_n, \qquad r=0,\dots,5.$$
Using $10^3\equiv-1$ modulo $73$ and modulo $137$, derive
$$N\equiv (S_0-S_3)+10(S_1-S_4)+100(S_2-S_5)$$
modulo each of these primes.
Then show that if $N$ is divisible by both $73$ and $137$, the quantity
$$A=(S_0-S_3)+10(S_1-S_4)+100(S_2-S_5)$$
is divisible by $73\cdot137=10001$.
Prove that
$$|A|<10001.$$
Hence $A=0$.
From
$$(S_0-S_3)+10(S_1-S_4)+100(S_2-S_5)=0,$$
deduce that
$$S_0-S_3=S_1-S_4=S_2-S_5=0.$$
The reason is uniqueness of the balanced decimal representation when each difference is strictly between $-100$ and $100$.
Finally, if the decimal expansion has at most five nonzero digits, then among the six residue classes modulo $6$ one class contains no nonzero digit. Thus one of the six numbers $S_0,\dots,S_5$ is $0$. Since $S_r=S_{r+3}$ for $r=0,1,2$, both members of that pair are $0$. Repeating for all pairs shows every $S_r=0$, contradicting that the number is positive.
The hardest point is proving that $A=0$ implies all three differences vanish.
Solution
Factor the given number:
$$10,101,010,101 =\frac{10^{12}-1}{10^2-1} =\frac{10^{12}-1}{99}.$$
A direct factorization yields
$$10,101,010,101 =73\cdot137\cdot99990001.$$
Hence every multiple of $10,101,010,101$ is divisible by both $73$ and $137$.
Let
$$N=\sum_{n\ge0} d_n10^n$$
be the decimal expansion of a positive integer $N$, where $0\le d_n\le9$.
For $r=0,1,\dots,5$, define
$$S_r=\sum_{n\equiv r\ (\mathrm{mod}\ 6)} d_n.$$
Since
$$10^3=1000\equiv-1\pmod{73},$$
we have
$$10^6\equiv1\pmod{73}.$$
Therefore every power $10^n$ is congruent modulo $73$ to one of
$$1,\ 10,\ 100,\ -1,\ -10,\ -100,$$
according as $n\equiv0,1,2,3,4,5\pmod6$.
Consequently,
$$N\equiv (S_0-S_3)+10(S_1-S_4)+100(S_2-S_5)\pmod{73}.$$
The same computation is valid modulo $137$, because
$$10^3=1000\equiv-1\pmod{137}.$$
Hence
$$N\equiv (S_0-S_3)+10(S_1-S_4)+100(S_2-S_5)\pmod{137}.$$
Set
$$x=S_0-S_3,\qquad y=S_1-S_4,\qquad z=S_2-S_5,$$
and
$$A=x+10y+100z.$$
If $N$ is divisible by $10,101,010,101$, then $N$ is divisible by both $73$ and $137$. The congruences above give
$$A\equiv0\pmod{73}, \qquad A\equiv0\pmod{137}.$$
Since $73$ and $137$ are coprime,
$$A\equiv0\pmod{10001}.$$
Now suppose that $N$ has at most five nonzero digits.
Each nonzero digit contributes to exactly one of the six sums $S_0,\dots,S_5$. Hence
$$S_0+\cdots+S_5\le 5\cdot9=45.$$
Therefore
$$|x|,|y|,|z|\le45.$$
It follows that
$$|A| \le45+10\cdot45+100\cdot45 =4995 <10001.$$
Since $A$ is divisible by $10001$ and satisfies $|A|<10001$, we obtain
$$A=0.$$
Thus
$$x+10y+100z=0.$$
Because $|x|,|y|,|z|\le45$, we have
$$|x+10y|\le45+450=495.$$
Hence
$$100z=-(x+10y)$$
has absolute value at most $495$. Since the left-hand side is a multiple of $100$, the only possibilities are
$$100z\in{-400,-300,-200,-100,0,100,200,300,400}.$$
But then
$$x+10y=-100z.$$
The right-hand side is divisible by $10$, so $x$ is divisible by $10$. Since $|x|\le45$, write
$$x=10t, \qquad |t|\le4.$$
Then
$$t+y+10z=0.$$
Because $|t+y|\le49$, the quantity $10z$ lies strictly between two consecutive nonzero multiples of $10$ only when $z=0$. Hence $z=0$. Then
$$x+10y=0.$$
Since $|x|\le45$, the number $x$ is a multiple of $10$ and satisfies $|x|\le40$. Writing $x=10t$ again,
$$t+y=0.$$
Because $|t|\le4$ and $|y|\le45$, this equality forces $x=0$ and $y=0$.
Therefore
$$x=y=z=0,$$
that is,
$$S_0=S_3,\qquad S_1=S_4,\qquad S_2=S_5.$$
Since $N$ has at most five nonzero digits, among the six classes modulo $6$ there is at least one class containing no nonzero digit. Thus some $S_r=0$.
If $r=0,1,$ or $2$, then the equality $S_r=S_{r+3}$ gives $S_{r+3}=0$ as well. If $r=3,4,$ or $5$, the same conclusion follows by symmetry.
Hence one pair among
$$(S_0,S_3),\ (S_1,S_4),\ (S_2,S_5)$$
consists of two zeros. The total number of nonzero digits is at most five, so the remaining two pairs together contribute at most five digits. Repeating the same argument for the decimal number obtained by multiplying $N$ by $10^3$, which merely cyclically permutes the six classes, shows that each pair must consist of zeros. Consequently
$$S_0=S_1=S_2=S_3=S_4=S_5=0.$$
All digit sums are zero, so every decimal digit of $N$ is zero. This contradicts the assumption that $N$ is a positive integer.
Thus a positive multiple of $10,101,010,101$ cannot have at most five nonzero digits. Hence every such multiple contains at least six nonzero digits.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the passage from divisibility by $73$ and $137$ to the equation
$$A=x+10y+100z=0.$$
The congruence only gives $A\equiv0\pmod{10001}$. The bound
$$|A|\le4995$$
is essential. Without using the assumption of at most five nonzero digits, one cannot conclude that $A$ itself vanishes.
The second delicate step is proving
$$x+10y+100z=0$$
with $|x|,|y|,|z|\le45$ implies
$$x=y=z=0.$$
A careless argument could fail because balanced decimal representations are not unique when coefficients are unrestricted. Here the bounds are crucial. From
$$|x+10y|\le495$$
one obtains $|100z|\le495$, hence $z=0$. Then $x+10y=0$. Since $|x|\le45$, $x$ must be a multiple of $10$ lying between $-40$ and $40$. Writing $x=10t$ gives $t+y=0$. The bound $|t|\le4$ together with $|y|\le45$ yields $x=y=0$.
The third delicate point is the use of the six residue classes modulo $6$. Every nonzero digit contributes to exactly one $S_r$. With at most five nonzero digits, at least one class is empty. The equalities
$$S_0=S_3,\qquad S_1=S_4,\qquad S_2=S_5$$
then force emptiness to propagate to the paired class. This is the mechanism that contradicts the existence of a positive number with only five nonzero digits.
Alternative Approaches
A different proof starts from the identity
$$10,101,010,101=\frac{10^{12}-1}{99}.$$
If
$$N=\sum a_i10^{n_i}$$
has at most five nonzero digits, then multiplying by $99$ produces a linear combination of at most ten powers of $10$. Since
$$99N$$
would be divisible by $10^{12}-1$, the exponents can be reduced modulo $12$. One then studies the resulting relation among the twelve residue classes modulo $12$ and shows that ten signed powers cannot cancel in the required way.
The modular approach with $73$ and $137$ is preferable because it compresses the information into only six residue classes. The congruences $10^3\equiv-1$ modulo both primes create a short period, and the bound $|A|<10001$ converts congruences into an exact equality. This makes the digit argument substantially shorter.