ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 107771
Темы:    [ Десятичная система счисления ]
[ Арифметика остатков (прочее) ]
[ Индукция (прочее) ]
Сложность: 5-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Докажите, что для любого  k > 1  найдётся такая степень двойки, что среди k последних её цифр не менее половины составляют девятки.
(Например,  212 = ...96,  253 = ...992.)


Решение

  Лемма. При всех  k ≥ 1  число   22·5k–1 + 1  делится на 5k.
  Доказательство. Индукция по k. База  (k = 1)  очевидна.
  Шаг индукции.  22·5k–1 + 1 = 45k–1 + 1.  Пусть   a = 45k–1.  Тогда  45k + 1 = a5 + 1 = (a + 1)(a4a3 + a2a + 1)  делится на 5k+1, поскольку по предположению индукции
a + 1  делится на 5k, а  a4a3 + a2a + 1 ≡ (–1)4 – (–1)3 + (–1)2 – (–1) + 1 = 5 (mod 5).

  Итак, число  2k(22·5k–1 + 1) оканчивается не меньше, чем k нулями. Несложно убедиться, что при  k > 1  количество цифр числа 2k не превосходит k/2. Значит, среди последних k цифр числа 22·5k–1 + k не более k/2 цифр могут отличаться от 9.

Замечания

1. Похожими рассуждениями можно доказать, что числа 40, 41, 42,...,  45k–1 дают различные остатки при делении на 5k. Попробуйте доказать более общий факт:
если  x – 1  делится на pk  (p > 2  – простое,  k > 0),  но не делится на pk+1, то  xn – 1  делится на pk+r тогда и только тогда, когда n делится на pr. Это важное утверждение (лемма Гензеля) часто используется в теории чисел.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 57
Год 1994
вариант
Класс 11
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .