Motivation?

Wait can't we also just take $(px-1)^5$ which excludes only $p$ (since $p$ is invertible $\pmod{q}$ for any prime $q\neq p$)?

In the original problem there was also the condition that $P$ can't have any rational root.

I guess (x^2+x+1).(2x^3+1) satisfies,too. Excluding 2.

Easy? Because 5 is the smallest integer such that there exists a polynomial that has no rational root and has a root in mod p for every p, for example P(x)=(x^2-3)(x^3+3), now it is easy to see that P(5x) sastifies the condition.

BarisKoyuncu wrote:

splendid !

Ahh, ahh Turkey. Again, very nice NT; but quite similar to following: Original, PFTB. Similar, KMO 2013. Similar, Taiwan TST.

Here's a similar construction: Let $P(x)=((2x)^2+3)((2x)^3-3)$. We claim this polynomial works. Firstly, note that $P$ excludes $2$, as all of its outputs are odds. Now, let $p>2$ be a prime. We distinguish three cases. Case 1: $p=3$. Then, we may take $x=3$. Case 2: $p \equiv 1 \pmod 3$. Then, we claim that there exists a $y$ such that $p \mid y^2+3$. Indeed, this follows from Quadratic Reciprocity. Now, take $x$ such that $y \equiv 2x \pmod p$ (we may find such an $x$ since $p>2$). Case 3: $p \equiv 2 \pmod 3$. Then, we claim that there exists a $z$ such that $p \mid z^3-3$. Indeed, this follows by taking $z=3^{(2p-1)/3}$, since then $z^3 \equiv 3^{2p-1} \equiv 3 \cdot 9^{p-1} \equiv 3 \pmod p$. Now, take $x$ such that $z \equiv 2x \pmod p$. Hence this polynomial $P$ works, and we conclude.