|
|
 |
Условие
Докажите, что для любого 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)(a4 – a³ + a² – a + 1) делится на 5k+1, поскольку по предположению индукции a + 1 делится на 5k, а a4 – a³ + a² – a + 1 ≡ (–1)4 – (–1)³ + (–1)² – (–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, 4²,..., 45k–1 дают различные остатки при делении на 5k. Попробуйте доказать более общий факт:
если x – 1 делится на pk
(p > 2 – простое, k > 0), но не делится на pk+1, то xn – 1 делится на pk+r тогда и только тогда, когда n делится на pr. Это важное утверждение (лемма Гензеля) часто используется в теории чисел.
