Заметим следующее:
a ≡ b (mod k) ⇒ aⁿ ≡ bⁿ (mod k)
Доказывается это следующим образом:
Пусть b = tk + a, тогда разложим (tk + a)ⁿ по Биному Ньютона. Все слагаемые кроме aⁿ имеют множитель k, следовательно, делятся на k, из чего:
(tk + a)ⁿ ≡ aⁿ (mod k).
А кроме этого заметим, что:
a ≡ a - k (mod k).
При данных двух утверждений докажем исходную задачу:
1²⁰¹⁹ + 2²⁰¹⁹ + ... + 29²⁰¹⁹ + 30²⁰¹⁹ ≡₃₁ 1²⁰¹⁹ + 2²⁰¹⁹ + ... + 15²⁰¹⁹ + (-15)²⁰¹⁹ + ... + (-2)²⁰¹⁹ + (-1)²⁰¹⁹ ≡₃₁ 0.
Значит, данная сумма кратна 31.
