Положим $f_1(x)=x^3-x+1$, и для каждого $n=2$, 3, $\ldots$
$$f_n(x)=f(f_{n-1}(x)).$$
Тогда $f_1(0)=f_1(1)=1$ и (по индукции) $f_n(0)=f_n(1)=1$ для каждого $n$.
Таким образом, свободный член $f_n(0)$ многочлена $f_n(x)$ с целыми коэффициентами равен 1.
Поэтому при любом натуральном $n$ и целом $a$ число $f_n(a)$ даёт при делении на $a$ остаток 1.
Отсюда следует, что при любых целых $k\gt l\gt0$ и $m$ число $f_k(m)=f_{k-l}(f_l(m))$ при делении на $f_l(m)$ даёт в остатке 1, так что $f_k(m)$ и $f_l(m)$ взаимно просты.
$$
\begin{array}{l}
x(x-1)\,r(x)+1;\\
x(x+1)[(x-1)\,r(x)-1]+1;\\
x[(x^2-1)\,r(x)-2x]+1;\\
x(x-1)[(x+1)\,r(x)+1]-1;\\
r[(x^2-1)\,r(x)+2x]-1;\\
x(x+1)\,r(x)-1
\end{array}
$$
(здесь $r(x)$ — произвольный многочлен с целыми коэффициентами).
Возникает естественный вопрос: каков должен быть многочлен $f(x)$ с целыми коэффициентами, чтобы для него выполнялось условие задачи:
$$
\begin{array}{c}
\textit{для любого натурального}~m\\
\textit{числа}~m{,}~f(m){,}~f(f(m)){,}~{\ldots}\\
\textit{попарно взаимно просты}.
\end{array}\tag{*}
$$
Из нашего решения ясно, что для этого достаточны условия $f(0)=f(1)=1$, другими словами, любой многочлен вида
$f(x)=x(x-1)\,r(x)+1$ (где $r(x)$ — любой многочлен с целыми коэффициентами) удовлетворяет условию (*).
Оказывается, полный ответ на наш вопрос таков: многочлен $f(x)$ удовлетворяет условию (*) тогда и только тогда, когда он принадлежит одному из шести типов, приведённых на полях.
Заметим, что в решении задачи мы построили бесконечную последовательность натуральных чисел, в которой все числа попарно взаимно просты (например: 2, $f_1(2)=7$, $f_2(2)=f_1(7)=337$, $\ldots$, $f_n(2)$, $\ldots$).
Из существования такой последовательности сразу вытекает бесконечность множества простых чисел.
