[ Arithmetic progression ] [ Arithmetic of residues (other) ]

## Author: Shapovalov A.B.

Petya added a natural number $\mathrm{N}$ to a natural number $\mathrm{M}$ and noticed that the sum of the digits of the result is the same as that of N. Then he added M to the result again, then once more, and so on. Is it necessarily true that he will eventually get a number with the same sum of digits as N again?
Example. Let $\mathrm{N}=2, \mathrm{M}=1008$. The number $\mathrm{M}$ is divisible by 16, so all numbers obtained by Petya give a remainder of 2 modulo 16. A number with a digit sum of 2 can be represented as the sum of two powers of ten. The powers $1, 10, 10^{2}$, and $10^{3}$ give remainders of 1, 10, 4, and 8 when divided by 16, respectively, and the other powers are multiples of 16. The remainder 2 can only be obtained in two ways: $1+1$ or $10+8$, which correspond to the numbers 2 and 1010. Therefore, Petya cannot obtain any other numbers with a digit sum of 2.

## Answer

not necessarily.