Олимпиадная задача по теории чисел и системам счисления для 9–11 классов: степень двойки с девятками

  Лемма. При всех  k ≥ 1  число   2^2·5k–1 + 1  делится на 5^k.

  Доказательство. Индукция по k. База  (k = 1)  очевидна.

  Шаг индукции.  2^2·5k–1 + 1 = 4^5k–1 + 1.  Пусть   a = 4^5k–1.  Тогда  4^5k + 1 = a⁵ + 1 = (a + 1)(a⁴ – a³ + a² – a + 1)  делится на 5^k+1, поскольку по предположению индукции  a + 1  делится на 5^k, а  a⁴ – a³ + a² – a + 1 ≡ (–1)⁴ – (–1)³ + (–1)² – (–1) + 1 = 5 (mod 5).   Итак, число  2^k(2^2·5k–1 + 1) оканчивается не меньше, чем k нулями. Несложно убедиться, что при  k > 1  количество цифр числа 2^k не превосходит ^k/₂. Значит, среди последних k цифр числа 2^{2·5k–1 + k} не более ^k/₂ цифр могут отличаться от 9.

Ответ задачи отсутствует