Разделы 
Дополнительно
Задача по математике - 3356
2019-06-02 
Докажите, что не существует многочлена степени не ниже двух с целыми неотрицательными коэффициентами, значение которого при любом простом $p$ является простым числом.
Решение:
Предположим, что такой многочлен $Q(x)$ существует. Пусть $Q(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0$, где $a_0, a_1, \cdots, a_n$ - целые неотрицательные числа, $a_n \neq 0, n \geq 2$.
Если $a_0 = 0$, то $Q(x) = x(a_nx^{n-1} + a_{n-1}x^{n-2} + \cdots + a_1)$, следовательно, при простом $p$ число $Q(p)$ делится на $p$, причем $Q(p) > p$ (здесь используется то, что степень $Q$ не меньше 2), поэтому $Q(p)$ - число составное. Допустим, $a_0 \geq 2$. Обозначим через $p$ некоторый простой делитель числа $a_0$. Тогда $Q(p) = (a_np^{n-1} + a_{n-1}p^{n-2} + \cdots + a_1)p + a_0$ делится на $p$, причем $Q(p) > p$; значит, $Q(p)$ - число составное. Таким образом, имеется единственная возможность: $a_0 = 1$.
Если для любого простого $p$ число $Q(p)$ простое, то и число $Q(Q(p))$ является простым при любом простом $p$. Значит, свободный член многочлена $Q(Q(x))$ должен равняться 1. Однако, поскольку $Q(0) = a_0 = 1, Q(Q(0)) = Q(1) = a_n + a_{n-1} + \cdots + a_1 +1 > 1$. Мы получили противоречие, завершающее доказательство.
Докажите, что не существует многочлена степени не ниже двух с целыми неотрицательными коэффициентами, значение которого при любом простом $p$ является простым числом.
Решение:
Предположим, что такой многочлен $Q(x)$ существует. Пусть $Q(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0$, где $a_0, a_1, \cdots, a_n$ - целые неотрицательные числа, $a_n \neq 0, n \geq 2$.
Если $a_0 = 0$, то $Q(x) = x(a_nx^{n-1} + a_{n-1}x^{n-2} + \cdots + a_1)$, следовательно, при простом $p$ число $Q(p)$ делится на $p$, причем $Q(p) > p$ (здесь используется то, что степень $Q$ не меньше 2), поэтому $Q(p)$ - число составное. Допустим, $a_0 \geq 2$. Обозначим через $p$ некоторый простой делитель числа $a_0$. Тогда $Q(p) = (a_np^{n-1} + a_{n-1}p^{n-2} + \cdots + a_1)p + a_0$ делится на $p$, причем $Q(p) > p$; значит, $Q(p)$ - число составное. Таким образом, имеется единственная возможность: $a_0 = 1$.
Если для любого простого $p$ число $Q(p)$ простое, то и число $Q(Q(p))$ является простым при любом простом $p$. Значит, свободный член многочлена $Q(Q(x))$ должен равняться 1. Однако, поскольку $Q(0) = a_0 = 1, Q(Q(0)) = Q(1) = a_n + a_{n-1} + \cdots + a_1 +1 > 1$. Мы получили противоречие, завершающее доказательство.
