4 $[$ Modular Arithmetic (other) $]$

Do there exist two consecutive natural numbers such that the sum of the digits of each of them is divisible by $125?$

Find the smallest pair of such numbers or prove that they do not exist.

#
When carrying over a digit in a number that ends exactly with $k$ nines, the sum of the digits decreases by $9k-1$. Let $N=\overline{a_{1} \ldots a_{n} \underbrace{9 \ldots 9}_{k}}$ be the smaller number in the desired pair $\left(a_{n} \neq 9\right)$. Then $9k-1$ is divisible by 125. Therefore, $9k \equiv 1 \pmod{125}$. Denote by $S(X)$ the sum of the digits of the number $X$. Since $S(N) \equiv 0 \pmod{125}$ and $S(\underbrace{9 \ldots 9}_{k}) \equiv 1 \pmod{125}$, then $S\left(\overline{a_{1} \ldots a_{n}}\right) = S(N) - S(\underbrace{9 \ldots 9}_{k}) \equiv 124 \pmod{125}$. Thus, the numbers $S(N)$ and $S(N+1)$ are divisible by 125 if and only if $9k \equiv 1 \pmod{125}$ and $S\left(\overline{a_{1} \ldots a_{n}}\right) \equiv 124 \pmod{125}$.

Since the conditions on the numbers $k$ and $\overline{a_{1} \ldots a_{n}}$ are independent, we can minimize $k$ and $\overline{a_{1} \ldots a_{n}}$ separately. From $9k \equiv 1 \equiv 126 \pmod{125}$, it follows that $k \equiv 14 \pmod{125}$, and thus the smallest possible value of $k$ is 14.

Since $a_{1} + \ldots + a_{n} \equiv 124 \pmod{125}$, we have $a_{1} + \ldots + a_{n} \geq 124$. Considering that $a_{i} \leq 9$, we get that $n \geq 14$.

Since a number with more digits is always greater than a number with fewer digits, in the desired pair $n=14$. Therefore, among the digits $a_{1}, \ldots, a_{n}$, either one is a seven and the rest are nines, or two are eights and the rest are nines. The digit $a_{1}$ cannot be 7, because in this case $a_{n} = a_{14} = 9$. Thus, the minimum value of $a_{1}$ is 8. Considering that in this case the number $\overline{a_{1} \ldots a_{n}}$ has exactly two eights, one of which must be in the last position and the other in the first, we get that the minimum value of $\overline{a_{1} \ldots a_{n}}$ is $8 \underbrace{9 \ldots 9}_{12}$. Therefore, the minimum value of $N$ is $8 \underbrace{9 \ldots 9}_{12} 8 \underbrace{9 \ldots 9}_{14}$.

## Answer

![](https://cdn.mathpix.com/cropped/2024_05_06_d9b26d382f9c77aca61cg-18.jpg?height=102&width=250&top_left_y=2078&top_left_x=10)

Send a comment