олимпиада - Целочисленный многочлен

Нет, не существует. Пусть P(1) = p - простое число, обозначим Q(x) = P(x + 1), имеем Q(0) = p. Тогда числа $%Q(p) = P(p-1), Q(2p) = P(2p-1), ..., Q(kp) = P(kp-1), ...$% делятся на p. Ясно, что не все они равны p, так что некоторые из них не простые.

Дополнение. Коэффициенты многочлена могут быть нецелыми числами. Но они рациональны. Действительно, пусть искомый многочлен имеет вид $%P(x) = a_nx^n + a_{n-1}x^{n-1}+ ... + a_0$%. Если x - натуральное число, то и P(x) - натуральное (даже простое), так что коэффициенты являются решениями системы уравнений с коэффициентами при неизвестных $%a_k$% вида $%(m^n, m^{n-1}, ... 1)$% при m от 1 до n+1. Как известно, определитель такой системы не равен 0, так что она имеет (единственное) рациональное решение.
Пусть $%a_k={p_k\over q_k}$% и $%N= НОК(q_1, q_2, ... q_{n+1})$%. Рассмотрим значения многочлена P(x) в точках $%m = N l$%. Если рассматривать его как многочлен $%Q(l) = P(Nl)$%, то коэффициенты многочлена Q будут уже целыми. Так что к Q можно применить приведенное выше рассуждение.