Problem

Source: Iranian 3rd round 2016 first number theory exam

Tags: number theory, algebra, polynomial



Let $P$ be a polynomial with integer coefficients. We say $P$ is good if there exist infinitely many prime numbers $q$ such that the set $$X=\left\{P(n) \mod q : \quad n\in \mathbb N\right\}$$has at least $\frac{q+1}{2}$ members. Prove that the polynomial $x^3+x$ is good.