делимость 123...n на 41

[maxal]

Пусть $f(n)$ равно конкатенации десятичных записей натуральных чисел от 1 до $n$. Например, $f(11)=1234567891011$ и т.п.

Докажите, что если $n$ - пятизначное число, то $f(n)$ не делится на 41.

[Хорхе]

(идея)

По модулю $41$ для пятизначных $f(n+1)=f(n)+n+1$. Ну и дальше на тему квадратичных невычетов; лень искать $f(10000)$.

[Руст]

Надо заметить, что $10^5=1\mod 41[math]$. Соответственно $f(n)=f(9999)+\frac{k(k-1)}{2}\mod 41=\frac{8f(9999)+(2k-1)^2}{8}\mod 41, k=n-10000$.
Поэтому достаточно проверить, что $(\frac{f(9999)}{41})=-1$, так как -1 и 2 квадратичные вычеты по модулю 41. Вычислить $f(9999)$ по модулю 41 не сложно, но лень.

[putnik]

При решении задачи используются два свойства числа 41:
1) Если от натурального числа а отрезать справа 5 цифр и полученные числа сложить, то остаток от деления на 41 не изменится.
2) Числа вида 11111, 101010101, 1001001001001 и т.д. делятся на 41 (а значит, пятикратная запись любого числа образует число, кратное 41).

Найдём f(9999) по модулю 41.
По mod 41
$f(9999)=1234 \cdot2+1020304 \cdot18+1002003004 \cdot180+1000200030004 \cdot1800=4 \cdot2+19 \cdot18+27 \cdot180+1 \cdot1800=-1.$
Тогда по mod 41$f(n)=f(9999)+(n+1000)(n-9999)/2=-1+(n^2+n-2)/2=(n^2+n-4)/2$ - не равно 0 ни при каких n.