Докажите, что число 1²⁰¹⁹+2²⁰¹⁹+3²⁰¹⁹++30²⁰¹⁹ кратно 31

Заметим следующее:

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.