Задача 30646

Тема:    [ Десятичная система счисления ]

Сложность: 4+ Классы: 8,9

Условие

К числу справа приписывают тройки. Докажите, что когда-нибудь получится составное число.

Решение

Пусть $N$ – изначальное число с одной приписанной тройкой. Поскольку $N$ оканчивается на $3$, оно взаимно просто с $10$.

Покажем, что найдётся число из одних единиц, кратное $N$. Действительно, рассмотрим числа $1$, $11$, ..., $\underbrace{11...1}_{N+1}$ – всего $N+1$ число, а различных остатков от деления на $N$ только $N$. Значит, два из этих чисел дают одинаковые остатки при делении на $N$. Тогда их разность $$\underbrace{11...1}_{m} - \underbrace{11...1}_{n} = \underbrace{11...1}_{m-n} \cdot 10^n$$ делится на $N$. Поскольку $N$ и 10 взаимно просты, на $N$ делится число $\underbrace{11...1}_{m-n}.$

Остаётся заметить, что тогда и $\underbrace{33...3}_{m-n} = 3 \cdot \underbrace{11...1}_{m-n}$ делится на $N$, а значит, если мы припишем справа к $N$ ещё $m-n$ троек, то результат будет делиться на $N$.

Источники и прецеденты использования

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	10
Название	Делимость-2
Тема	Теория чисел. Делимость
задача
Номер	060