Selection Examinations for the IMO

Obviously, such a polynomial exists for $n=1$. In this case the only condition is that $P(1)=1$ and the polynomial $P(x)=x$ has this property.

If $n$ is a prime, then its only two divisors are $1$ and $n$. The polynomial $P$ must satisfy the conditions $P(1)=n^2$ and $P(n)=1$. Let us write $P(x)=ax+b$ and solve the resulting system of equations. We get $P(x)=(-p-1)x+p^2+p+1$.

Assume that $n=k\cdot l$ is not a prime and $k,l>1$. We have $P(1)=n^2$, $P(l)=k^2$, $P(k)=l^2$ and $P(n)=1$. We know that for arbitrary integers $a$ and $b$ the number $P(a)-P(b)$ is divisible by $a-b$. So, $n-k=k(l-1)$ divides $P(n)-P(k)=1-l^2=(1-l)(1+l)$. This implies that $k$ divides $l+1$. Similarly, we show that $n-l$ divides $P(n)-P(l)$. So $l(k-1)$ divides $(1-k)(1+k)$ and $l$ divides $k+1$. Hence, $kl$ divides $(k+1)(l+1)$ and therefore it also divides $(k+1)(l+1)-kl=k+l+1$. We must have $kl\le k+l+1$, which implies that $kl-k-l+1\le 2$ or $(k-1)(l-1)\le 2$. We may assume that $k\le l$. The only possible case is $k=2$ and $l=3$, whence $n=6$.

Let us find a polynomial $P$, satisfying the conditions $P(1)=36$, $P(2)=9$, $P(3)=4$ and $P(6)=1$. For the polynomial $Q(x)=P(x)-1$ we have $Q(1)=35$, $Q(2)=8$, $Q(3)=3$ and $Q(6)=0$, so $6$ is a root of $Q$. Let us write $Q(x)=(x-6)R(x)$. For $R(x)$ we have $R(1)=-7$, $R(2)=-2$ and $R(3)=-1$, so $3$ is a root of the polynomial $R(x)+1$ and $R(x)=1+(x-3)S(x)$. For the polynomial $S(x)$ we have $S(1)=4$ and $S(2)=3$. We see that $S(x)=5-x$, whence $P(x)=1+(x-6)(1+(x-3)(x-5))$.