Олимпиадная задача по теории чисел и индукции для 10-11 классов: делимость суммы

  Лемма 1.   k²ⁿ ≡ 1  (mod 2ⁿ⁺²)   для каждого нечётного числа k.

  Доказательство.   k²ⁿ – 1 = (k – 1)(k + 1)(k² + 1)(k⁴ + 1)...(k^2n–1 + 1)   – произведение  n + 1  чётных множителей. Вдобавок один из первых двух множителей делится на 4.   Лемма 2.   (k + 2ⁿ)^k ≡ k^k(1 + 2ⁿ)  (mod 2ⁿ⁺²)   при  n > 1.

  Доказательство.     а все слагаемые, кроме двух первых, делятся на 2ⁿ⁺².   Вернёмся к решению задачи. Обозначим сумму из условия через S_n, а разность  S_n+1 – S_n  через R_n. Будем вести индукцию по n.

  База  (n = 2)  очевидна.

  Шаг индукции.  S_n+1 = S_n + R_n.  R_n есть сумма 2^n–1 слагаемых вида m^m, где  m = 2ⁿ + k,  k – нечётное число, меньшее 2ⁿ. По лемме 1

m^m ≡ m^k  (mod 2ⁿ⁺²).  Поэтому   R_n ≡ (1 + 2ⁿ) + (3 + 2ⁿ)³ + (5 + 2ⁿ)⁵ + ...  (mod 2ⁿ⁺²).

  По лемме 2   R_n ≡ S_n(1 + 2ⁿ) (mod 2ⁿ⁺²).   Значит,   S_n+1 ≡ 2S_n(1 + 2^n–1)  (mod 2ⁿ⁺²).

  По предположению индукции S_n делится на 2ⁿ (значит, S_n+1 делится на 2ⁿ⁺¹) и не делится на 2ⁿ⁺¹ (значит, S_n+1 не делится на 2ⁿ⁺²).

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