Сделаем сначала замечание, общее для всех трёх решений. Пусть $p$ — нечётное простое число, а $a < p$ — натуральное число такое, что $a^2 + 1$ делится на $p$; тогда числа $a$ и $p-a$ различны, и $P(a) = P(p-a) = p$. Действительно, числа $a^2 + 1$ и $(p-a)^2 + 1 = (a^2 + 1) + p(p - 2a)$ делятся на $p$ и меньше $p^2$; значит, они не могут делиться на простые числа, большие $p$.

Первое решение. Предположим противное. Тогда существует лишь конечное число простых чисел $p$, для которых уравнение $P(x) = p$ имеет хотя бы три натуральных решения. Обозначим через $s$ максимальное такое простое число (если таких простых не существует, положим $s = 2$), а через $S$ — произведение всех простых чисел, не превосходящих $s$.

Пусть $p = P(S)$; тогда $p$ взаимно просто с $S$ и потому $p > s$. Пусть $a$ — остаток от деления $S$ на $p$; тогда $a^2 + 1$ делится на $p$, значит, $P(a) = P(p-a) = p$. Одно из чисел $a$ и $p-a$ чётно; обозначим его через $b$.

Далее, число $(b+p)^2 + 1$ делится на $2p$ (ибо $b$ чётно, а $p$ нет), поэтому $P(b+p) \ge p$. Если $P(b+p) = p$, то уравнение $P(x) = p$ имеет три решения $-b, p-b, p+b$; это невозможно по предположению. Значит, $P(b+p) = q > p$, число $(b+p)^2 + 1$ делится на $2pq$ и потому не меньше, чем $2pq$. Это означает, что $q < b+p$ (в противном случае $(b+p)^2 + 1 \le (2p-1)q + 1 < 2pq$).

Наконец, обозначая через $c$ остаток от деления числа $b+p$ на $q$, получаем $P(c) = P(q-c) = P(b+p) = q > p > s$, что противоречит выбору $s$.

Второе решение. Мы будем использовать тождество
$$(m^2 + 1)((m-1)^2 + 1) = (m^2 - m + 1)^2 + 1, \quad (*)$$
которое можно проверить, например, раскрытием скобок. Из него следует, что $P(m^2 - m + 1) = \max(P(m), P(m+1))$.

Предположим противное. Пусть $N$ — наибольшее число, встречающееся в описанных тройках; если таких троек нет, то положим $N = 3$. Последовательность натуральных чисел $P(N+1), P(N+2), \dots$ не может строго убывать. Значит, найдётся число $n > N + 1$, для которого $P(n-1) \le P(n)$. Тогда $P(n^2-n+1) = \max(P(n), P(n-1)) = P(n)$. Поэтому найдётся число $n \le m \le n^2-n+1$ такое, что $P(m-1) \le P(m) \ge P(m+1)$; иначе $P(n-1) \le P(n) < P(n+1) < \dots < P(n^2-n+1)$, что не так.

Теперь из (*) имеем $P(m^2-m+1) = \max(P(m), P(m-1)) = P(m)$ и $P(m^2 + m + 1) = \max(P(m), P(m+1)) = P(m)$. Таким образом, тройка $m, m^2-m+1, m^2+m+1$ удовлетворяет условию, и $m > N$; противоречие с выбором числа $N$.

Третье решение. Для любого натурального $n \ge 1$ рассмотрим число $(2+\sqrt{5})^{2n+1}$; оно имеет вид $a_n + b_n\sqrt{5}$ при некоторых натуральных $a_n, b_n$ (ясно, что $a_n < a_{n+1}$). Заметим, что тогда $(2 - \sqrt{5})^{2n+1} = a_n - b_n\sqrt{5}$, откуда
$$a_n^2 - 5b_n^2 = (a_n + b_n\sqrt{5})(a_n - b_n\sqrt{5}) = ((2+\sqrt{5})(2-\sqrt{5}))^{2n+1} = -1.$$
Тогда $a_n^2 + 1 = 5b_n^2$; ясно, что $b_n < a_n$ и $a_n \ge 2^{2n+1} \ge 8$, поэтому все простые делители числа $a_n^2 + 1$ не превосходят $\max(5, b_n) < a_n$.

Итак, $p_n = P(a_n) < a_n$. С другой стороны, $a_n^2 + 1 = 5$, значит, $p_n \ge 5$. Обозначим теперь через $c_n$ остаток от деления $a_n$ на $p_n$. Тогда числа $c_n, p_n - c_n, a_n$ различны и $P(c_n) = P(p_n - c_n) = P(a_n)$. Мы предъявили бесконечно много различных троек требуемого вида.