Задача 73741

Темы:    [ Деление с остатком ] [ Принцип Дирихле (прочее) ] [ Десятичная система счисления ] [ НОД и НОК. Взаимная простота ]

Сложность: 4- Классы: 9,10,11

Условие

Автор: Уфнаровский В.А.

Дана бесконечная последовательность цифр. Докажите, что для любого натурального числа n, взаимно простого с числом 10, можно указать такую группу стоящих подряд цифр последовательности, что записываемое этими цифрами число делится на n.

Решение

  Будем считать, что нам задана бесконечная последовательность цифр a₁, a₂, ..., a_i, ..., записанная слева направо. Рассмотрим числа: a_m,  a_m–1a_m,  a_m–2a_m–1a_m,  ...,  a₁a₂...a_m  (черта, как обычно, обозначает десятичную запись числа). Если  m > n,  то найдутся два числа  a_m–i...a_m  и  a_m–j...a_m,  где
i < j,  дающие при делении на n одинаковый остаток. Поэтому их разность  a_m–j...a_m–i–10...0 = 10ⁱ⁺¹·a_m–j...a_m–i–1  делится на n.
  По условию n и 10 взаимно просты, следовательно,  a_m–j...a_m–i–1  делится на n.

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

журнал
Название	"Квант"
год
Год	1973
выпуск
Номер	6
Задача
Номер	М206