Local Mathematical Competitions

Clearly a constant non-null polynomial $P$ fulfills the requirements, so we shall assume in the sequel $\mathrm{deg}P\ge 1$. Before further proceeding with the solution, we state the following "folklore" preliminaries. (1) Dirichlet's Theorem. The arithmetic progression $(an+b{)}_{n\in \mathbb{N}}$ with $a\in {\mathbb{N}}^{\ast }$, $b\in {\mathbb{Z}}^{\ast }$, $(a,b)=1$, contains infinitely many primes. (2) "Fundamental" property of integer polynomials. For any $f\in \mathbb{Z}[X]$ and any $a,b\in \mathbb{Z}$ we have $a-b\mid f(a)-f(b)$. Claim. $P(0)=0$. We proceed by contradiction, thus assume $P(0)\ne 0$. We will prove by induction on $k$ the following statement For any $k\in {\mathbb{N}}^{\ast }$ there exists a prime $p>|P(0)|$ such that $P(p)$ has at least $k$ distinct prime factors. For $k=1$, there exists a prime $p_1>|P(0)|$ such that $|P(p_1)|\ne 1$, otherwise for all such primes $p$ we would have $P(p{)}^2=1$ and thus the polynomial $P(X{)}^2-1$ has infinitely many roots, thus it is the null polynomial, hence $P(X)\equiv 1(\mathrm{mod}p)$ or $P(X)\equiv -1(\mathrm{mod}p)$, contradicting $\mathrm{deg}P\ge 1$. Therefore $P(p_1)$ has at least one prime factor, so the statement is proven for $k=1$. Let $p_k$ be a prime with the property $p_k>|P(0)|$ and $P(p_k)$ has at least $k$ distinct prime factors. Let us notice that $(p_k,P(p_k))=1$, since from the "fundamental" property we have $P(p_k)\equiv P(0)(\mathrm{mod}{p}_k)$ and since $p_k>|P(0)|$ and it is a prime, the conclusion follows. The arithmetic progression $(nP(p_k{)}^2+p_k{)}_{n\in \mathbb{N}}$ (according to Dirichlet's Theorem) contains infinitely many primes. Let $p_{k+1}=sP(p_k{)}^2+p_k$ be such a prime. Then $P(p_{k+1})\equiv P(p_k)(\mathrm{mod}P(p_k{)}^2)$, thus there exists $t$ such that $P(p_{k+1})=P(p_k)(1+tP(p_k))$. From this it is obvious that $P(p_{k+1})$ has at least one more prime factor than $P(p_k)$. Since $P(p_k)$ had at least $k$ distinct prime factors, it follows that $P(p_{k+1})$ has at least $k+1$ prime factors. Thus the statement is proven and we get that the assumption $P(0)\ne 0$ is false. From $P(0)=0$ we deduce there exists $m$ so that $P(X)=X^{m}Q(X)$ with $Q(0)\ne 0$. If $Q$ would be nonconstant, arguing the same as in the above, we again obtain a contradiction. We conclude the only solutions are $P(X)=c{X}^m$, for some $m\in \mathbb{N}$ and $c\in {\mathbb{Z}}^{\ast }$.