THE Tenth ROMANIAN MASTER OF MATHEMATICS

To rule out all other values of $n$, it is sufficient to exhibit a monic polynomial $P$ of degree at most $n$ with integer coefficients, whose restriction to the integers is injective, and $P(x)\equiv 1(\mathrm{mod}n)$ for all integers $x$. This is easily seen by reading the relation in the statement modulo $n$, to deduce that $k\equiv 1(\mathrm{mod}n)$, so $k=1$, since $1\le k\le n$; hence $P(x_1)=P(x_2)$ for some distinct integers $x_1$ and $x_2$, which contradicts injectivity. If $n=1$, let $P=X$, and if $n=4$, let $P=X^4+7X^2+4X+1$. In the latter case, clearly, $P(x)\equiv 1(\mathrm{mod}4)$ for all integers $x$; and $P$ is injective on the integers, since $P(x)-P(y)=(x-y)((x+y)(x^2+y^2+7)+4)$, and the absolute value of $(x+y)(x^2+y^2+7)$ is either 0 or at least 7 for integral $x$ and $y$.

Finally, let $P=f_n+nX+1$ if $n$ is odd, and let $P=f_{n-1}+nX+1$ if $n$ is even. In either case, $P$ is strictly increasing, hence injective, on the integers, and $P(x)\equiv 1(\mathrm{mod}n)$ for all integers $x$.