Задача 3. 12345 много раз подряд

Что происходит, когда приписываем ещё одно 12345

Обозначим через $N_k$ число, в котором «$12345$» выписано $k$ раз подряд: $N_1=12345$, $N_2=1234512345$, и так далее. В числе $N_k$ ровно $5k$ цифр.

Как из $N_k$ получить $N_{k+1}$? Надо приписать справа пять цифр $12345$. Приписать справа пять нулей — значит умножить на $100000$, а потом поставить вместо нулей $12345$ — значит прибавить $12345$:

Проверим на $k=1$: $12345\cdot 100000+12345=1234500000+12345=1234512345=N_2$ (рисунок ниже).

Зачем это нужно: вместо огромного числа у нас короткое правило «умножь на $100000$ и прибавь $12345$». Теперь можно следить, что это правило делает с остатком при делении на $41$, — а остаток всегда маленький, от $0$ до $40$.

Число 100000 даёт остаток 1

Разделим $100000$ на $41$. Удобно заметить, что $11111=41\cdot 271$ (проверка: $41\cdot 271=41\cdot 270+41=11070+41=11111$). Тогда $99999=9\cdot 11111=41\cdot 2439$, и

Можно и просто разделить столбиком: $41\cdot 2439=41\cdot 2400+41\cdot 39=98400+1599=99999$, остаток $1$.

Почему это главное наблюдение: умножим любое число $N$ на $100000$:

Первое слагаемое делится на $41$, поэтому $N\cdot 100000$ даёт при делении на $41$ тот же остаток, что и $N$. Умножение на $100000$ — то есть «сдвиг числа на пять цифр влево» — остаток не меняет.

Как до этого догадаться: в правиле из шага 1 участвует $100000$, и первое, что стоит узнать про него, — его остаток при делении на $41$. Остаток $1$ — самый удобный из возможных.

Каждое новое 12345 прибавляет к остатку 4

Найдём остаток числа $12345$: $41\cdot 301=12341$, значит, $12345=41\cdot 301+4$ — остаток $4$.

Теперь посмотрим на правило $N_{k+1}=N_k\cdot 100000+12345$ с точки зрения остатков. Число $N_k\cdot 100000$ даёт тот же остаток, что $N_k$ (шаг 2); прибавить $12345=41\cdot 301+4$ — всё равно что прибавить $4$, потому что $41\cdot 301$ делится на $41$. Запишем это одной строкой:

Значит, $N_{k+1}$ и $N_k+4$ дают одинаковые остатки при делении на $41$: с каждой новой копией остаток увеличивается на $4$ (а когда переваливает за $40$, из него вычитается $41$).

Пройдём по шагам. $N_1=12345$ — остаток $4$. $N_2$ — остаток $8$, $N_3$ — $12$, …, $N_{10}$ — $40$, $N_{11}$ — $44-41=3$, $N_{12}$ — $7$ и так далее (рисунок ниже). Короче говоря, остаток числа $N_k$ равен остатку числа $4k$: для $k=1$ это так, а если это верно для $N_k$, то $N_{k+1}$ даёт тот же остаток, что $4k+4=4(k+1)$.

Когда 4k делится на 41

Число $N_k$ делится на $41$ тогда и только тогда, когда остаток нуль, то есть когда $4k$ делится на $41$.

Пусть $k\le 40$. Тогда $4\le 4k\le 160$, а кратные $41$ в этих пределах — только $41$, $82$ и $123$. Ни одно из них не делится на $4$: $41$ и $123$ нечётные, а $82=2\cdot 41$ делится на $2$, но не на $4$. Значит, $4k$ не кратно $41$ ни при каком $k$ от $1$ до $40$, и ни одно из чисел $N_1,\ldots,N_{40}$ на $41$ не делится.

При $k=41$ получаем $4k=164=41\cdot 4$ — делится. Значит, $N_{41}$ — число из $41$ копии, то есть из $205$ цифр, — делится на $41$.

Ответ: $41$ раз.

То же самое короче: $41$ — простое число, а $4$ на него не делится, поэтому $4k$ делится на $41$ только когда $k$ делится на $41$; наименьшее такое $k$ — само $41$. Полоска остатков на рисунке ниже показывает всё это сразу: нуль впервые появляется на $41$-м шаге.