|
|
 |
Условие
Дан многочлен P(x) с целыми коэффициентами, причём для каждого натурального x выполняется неравенство P(x) > x. Определим последовательность {bn} следующим образом: b1 = 1, bk+1 = P(bk) для k ≥ 1. Известно, что для любого натурального d найдется член последовательности {bn}, делящийся на d. Докажите, что P(x) = x + 1.
Решение
Заметим сначала, что если целые числа x и y дают одинаковые остатки при делении на натуральное число d, то P(x) и P(y) также дают одинаковые остатки при делении на d. Это следует из теоремы Безу для целочисленных многочленов (см. решение задачи 35562).
Пусть P(x) отличен от x + 1. Поскольку последовательность {bn} – из натуральных чисел и P(x) > x для каждого натурального x, при некотором натуральном n будет bn+1 > bn + 1. Возьмём минимальное такое n. Имеем: b1 = 1, b2 = 2, ..., bn = n, bn+1 > n + 1. Положим d = bn+1 − 1. Остатки от деления членов нашей последовательности на d вначале будут равны 1, 2, ..., n, а затем, в силу сделанного замечания и выбора d, они будут периодически повторяться: bn+1 даст в остатке 1, bn+2 даст 2, поскольку bn+2 = P(bn+1) ≡ P(b1) = b2 = 2 (mod d), аналогично, bn+3 даст 3, ..., b2n даст n, b2n+1 – снова 1 и т.д. Значит, ни один из членов последовательности, вопреки условию, не будет делиться на d. Противоречие.
