Сформулируем задачу по-другому. Пусть
$\{ T_n \}$ - последовательность чисел, в которой число
$T_n$ в десятичной записи является конкатенацией всех десятичных записей чисел от
$1$ до
$n$. Доказать, что в этой последовательности найдется число, делящееся на
$2017$. Это чуть более сильное утверждение, но с такой последовательностью работать удобнее. Вместо
$2017$ можно брать любое простое
$p$.
$T_{n+1} = T_n \cdot 10^x + (n + 1)$Будем рассматривать последовательность в том месте, где
$x$ уже достаточно большое и долго не будет меняться. Также нам не важны конкретные значения членов последовательности, а важны их остатки от деления на
$p$. С этим условием и без ограничения общности для некоторого
$n$ запишем
$T_{n + 1} = rT_n + 1$, где
$r = 10^x$.
$T_{n + 2} = r^2T_n + r + 2$$T_{n + k} = r^kT_n + \sum_{i=1}^{k}{ir^{k-i}} = r^kT_n + \sum_{i = 1}^{k}{\sum_{j = 0}^{k - i}{r^j}} = r^kT_n + \sum_{i=1}^{k}{\frac{r^{k-i+1}-1}{r-1}} = r^kT_n + \frac{r(r^k - 1) - k(r - 1)}{(r - 1)^2}$Теперь заметим, что в качестве
$r$ мы можем рассматривать не
$10^x$, а его остаток от деления на
$p$, то есть мы можем выбрать его произвольно от
$1$ до
$p - 1$ (по Малой Теореме Ферма). Выберем его равным
$2$.
$T_{n + k} = 2^k(T_n + 2) - (k + 2)$Обозначим
$t = T_n + 2$, и получим
$T_{n + k} = 2^kt - (k + 2)$. Будем считать, что
$t$ не делится на
$p$, мы всегда можем этого добиться. Выражение
$2^kt $ делится на
$p$ с остатками
$1, 2, .. (p-1)$ с периодичностью
$p - 1$. А выражение
$k +2 $ делится на
$p$ с остатками
$0, 1, 2, .. (p - 1)$ с периодичностью
$p$. Таким образом найдется
$k$, при котором эти остатки совпадут, а значит
$T_{n + k}$ разделится на
$p$.
