Kvant Math Problem 172
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m45s
Source on kvant.digital
Problem
Prove that for every prime $p$, the number $$\underbrace{11 \ldots 1}{p}\underbrace{22 \ldots 2}{p}\underbrace{33 \ldots 3}{p} \ldots \underbrace{99 \ldots 9}{p} - 123456789$$ is divisible by $p$.
M. L. Gerver
Exploration
Let
$$N=\underbrace{11\ldots1}{p}\underbrace{22\ldots2}{p}\underbrace{33\ldots3}{p}\cdots \underbrace{99\ldots9}{p}.$$
The statement is that $N-123456789$ is divisible by the prime $p$.
Write
$$R=\underbrace{11\ldots1}_{p}=1+10+\cdots+10^{p-1}.$$
Then each block of $p$ equal digits is $kR$, where $k=1,\dots,9$. Since the blocks have length $p$,
$$N=R\left(10^{8p}+2\cdot10^{7p}+\cdots+8\cdot10^p+9\right).$$
The natural idea is to work modulo $p$. For $p\neq2,5$, Fermat's theorem gives
$$10^p\equiv10\pmod p.$$
Also
$$R=\frac{10^p-1}{9}\equiv\frac{10-1}{9}\equiv1\pmod p.$$
Then
$$N\equiv 10^8+2\cdot10^7+\cdots+8\cdot10+9,$$
and the right-hand side is exactly $123456789$.
The special primes $2$ and $5$ must be checked separately because division by $9$ inside congruences is harmless, but Fermat's theorem does not apply in the same way when $10$ is not invertible modulo $p$.
For $p=2$,
$$N=112233445566778899,$$
whose last digit is $9$, so $N-123456789$ is even.
For $p=5$, every block has length $5$, so $N$ ends in $99999$; hence
$$N\equiv 4\pmod5.$$
Also
$$123456789\equiv4\pmod5.$$
Thus the difference is divisible by $5$.
The only potentially delicate step is proving $R\equiv1\pmod p$ for every prime $p\neq3$, and checking $p=3$ separately because $9$ is not invertible modulo $3$.
Problem Understanding
We are given a number obtained by writing $p$ copies of $1$, then $p$ copies of $2$, and so on up to $p$ copies of $9$. We must prove that subtracting $123456789$ from this number always yields a multiple of the prime $p$.
This is a Type B problem. The task is to prove a divisibility statement for all primes $p$.
The core difficulty is expressing the large decimal number in a form that allows reduction modulo $p$, while treating the exceptional primes $2,3,5$ correctly.
Proof Architecture
Let $R=1+10+\cdots+10^{p-1}$; then the given number equals
$$N=R\left(10^{8p}+2\cdot10^{7p}+\cdots+8\cdot10^p+9\right).$$
For $p=2$, prove directly that $N\equiv123456789\pmod2$.
For $p=5$, prove directly that $N\equiv123456789\pmod5$.
For $p=3$, show that $R\equiv1\pmod3$ by evaluating the geometric sum modulo $3$, then reduce the remaining factor modulo $3$.
For primes $p\neq2,3,5$, use Fermat's theorem $10^p\equiv10\pmod p$ and deduce $R=(10^p-1)/9\equiv1\pmod p$.
Substitute these congruences into the expression for $N$, obtaining
$$N\equiv10^8+2\cdot10^7+\cdots+8\cdot10+9=123456789\pmod p.$$
The most delicate point is the proof that $R\equiv1\pmod p$, especially when $p=3$, since division by $9$ modulo $3$ is invalid.
Solution
Let
$$R=1+10+10^2+\cdots+10^{p-1}.$$
Then a block consisting of $p$ copies of the digit $k$ equals $kR$. Hence
$$N = R\left(10^{8p}+2\cdot10^{7p}+3\cdot10^{6p}+4\cdot10^{5p} +5\cdot10^{4p}+6\cdot10^{3p}+7\cdot10^{2p}+8\cdot10^p+9\right).$$
We must prove
$$N\equiv123456789\pmod p.$$
First consider $p=2$. Since
$$N=112233445566778899,$$
both $N$ and $123456789$ are odd. Therefore
$$N-123456789\equiv0\pmod2.$$
Now consider $p=5$. The number $N$ ends in the digit $9$, so
$$N\equiv9\equiv4\pmod5.$$
Also
$$123456789\equiv4\pmod5.$$
Thus
$$N-123456789\equiv0\pmod5.$$
Next consider $p=3$. Since $10\equiv1\pmod3$,
$$R\equiv1+1+\cdots+1 \pmod3.$$
There are $3$ summands, so
$$R\equiv3\equiv0\pmod3.$$
Consequently,
$$N\equiv0\pmod3.$$
The sum of the digits of $123456789$ is
$$1+2+\cdots+9=45,$$
which is divisible by $3$. Hence
$$123456789\equiv0\pmod3.$$
Therefore
$$N-123456789\equiv0\pmod3.$$
It remains to consider primes $p\neq2,3,5$.
By Fermat's little theorem,
$$10^p\equiv10\pmod p.$$
Since $9$ is invertible modulo $p$,
$$R=\frac{10^p-1}{9} \equiv \frac{10-1}{9} = 1 \pmod p.$$
Also,
$$10^{kp}=(10^p)^k\equiv10^k\pmod p$$
for every integer $k\ge0$.
Substituting these congruences into the expression for $N$, we obtain
$$\begin{aligned} N &\equiv 10^8+2\cdot10^7+3\cdot10^6+4\cdot10^5 \ &\qquad +5\cdot10^4+6\cdot10^3+7\cdot10^2+8\cdot10+9 \pmod p. \end{aligned}$$
The right-hand side is precisely the decimal expansion of $123456789$. Hence
$$N\equiv123456789\pmod p.$$
Therefore
$$p\mid\bigl(N-123456789\bigr)$$
for every prime $p$.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the reduction of $R$ modulo $p$. For primes $p\neq2,3,5$,
$$R=\frac{10^p-1}{9}.$$
Fermat's theorem gives $10^p\equiv10\pmod p$. Since $p\neq3$, the number $9$ has a multiplicative inverse modulo $p$, so
$$R\equiv\frac{10-1}{9}=1\pmod p.$$
For $p=3$, this argument is invalid because $9\equiv0\pmod3$. The value of $R$ must instead be computed from the sum $1+10+\cdots+10^{p-1}$, yielding $R\equiv0\pmod3$.
The second delicate step is the congruence
$$10^{kp}\equiv10^k\pmod p.$$
It follows from
$$10^{kp}=(10^p)^k$$
and $10^p\equiv10\pmod p$. Replacing each factor $10^{kp}$ by $10^k$ is therefore justified term by term.
The third delicate step is identifying the resulting expression with $123456789$. Indeed,
$$10^8+2\cdot10^7+\cdots+8\cdot10+9$$
is exactly the decimal number whose digits are $1,2,\ldots,9$, namely $123456789$.
Alternative Approaches
Instead of introducing $R$, one may write the block of $p$ copies of the digit $k$ as
$$k\frac{10^p-1}{9}.$$
Then
$$N=\frac{10^p-1}{9}\left(10^{8p}+2\cdot10^{7p}+\cdots+8\cdot10^p+9\right).$$
For primes $p\neq2,3,5$, Fermat's theorem immediately converts $(10^p-1)/9$ to $1$ modulo $p$ and each $10^{kp}$ to $10^k$. The proof then finishes exactly as above, with the exceptional primes checked separately.
Another route is to work with the polynomial
$$f(x)=(1+x+\cdots+x^{p-1}) (x^8+2x^7+\cdots+8x+9)$$
and evaluate it at $x=10$. Modulo $p$, Fermat's theorem implies $10^p\equiv10$, so the first factor becomes $1$, while every exponent $kp$ in the expanded form collapses to $k$. This again yields $f(10)\equiv123456789\pmod p$. The direct congruence computation with $R$ is shorter and keeps the decimal structure transparent.