Задача 110175
|
|
 |
Условие
Докажите, что для любого многочлена P с целыми коэффициентами и любого натурального k существует такое натуральное n, что P(1) + P(2) + ... + P(n) делится на k.
Решение
Заметим, что числа P(r) и P(mk + r) дают одинаковые остатки при делении на k (см. решение задачи 35562). Следовательно, в сумме
P(1) + P(2) + ... + P(k²) для каждого r = 0, 1, ..., k – 1 будет k слагаемых вида P(mk + r), дающих одинаковые остатки при делении на k. Сумма этих k слагаемых делится на k; сумма всех k² слагаемых разбивается на k таких сумм, а потому тоже делится на k.
