Задача
NT-B2-M12-P003 Остатки многочлена периодичны
#3
★★☆☆☆ Уровень 2 из 5
Пусть \(f\in\mathbb Z[x]\), \(m\ge1\). Докажите, что последовательность \(f(0),f(1),f(2),\ldots\) по модулю \(m\) имеет период \(m\).
Сравните \(n+m\) и \(n\) по модулю \(m\).
Так как \(n+m\equiv n\pmod m\), для каждого одночлена \((n+m)^k\equiv n^k\pmod m\). Значит, \(f(n+m)\equiv f(n)\pmod m\). Поэтому остатки повторяются с периодом \(m\) (возможно, не минимальным).
Важно слово “имеет период”, а не “минимальный период”.