Find all $P \in \mathbb{Z}[X]$, such that $P(n)$ divides $n^{n-1}-1$ for all $n \geqslant 2001$.
Answer: $P(n)= \pm 1, P(n)= \pm(n-1)$ and $P(n)= \pm(n-1)^{2}$.

We know that $a-b \mid P(a)-P(b)$ for $a$ and $b$ two integers, given that $P \in \mathbb{Z}[X]$. Therefore, $n+P(n)-n \mid P(n+P(n))-P(n)$, or equivalently, since $P(n) \mid P(n)$, we have $P(n) \mid P(n+P(n))$.

Thus, $P(n) \mid P(n+P(n)) \mid n^{n+P(n)-1}-1$. We also have $P(n) \mid (n^{n-1}-1) n^{P(n)}$, and by subtracting the last two expressions on the right, we find that $P(n) \mid n^{P(n)}-1$.

We now use the following lemma: $\operatorname{PGCD}\left(a^{m}-1, a^{n}-1\right)=a^{\operatorname{PGCD}(m, n)}-1$ (a known lemma whose proof is left to the reader). Thus, $P(n)$ divides $\operatorname{PGCD}\left(n^{n-1}-1, n^{P(n)}-1\right)=n^{\operatorname{PGCD}(P(n),(n-1))}-1$. We now take $n \geqslant 2001$ such that $n-1$ is prime. If $P(n)$ is not divisible by $n-1$, then we obtain that $P(n)$ divides $n^{\operatorname{PGCD}(P(n),(n-1))}-1=n-1$. Therefore, either $P(n)= \pm 1$ for infinitely many $n$, or $P(n)= \pm 1$ for all $n$, or $P(n)$ is divisible by an infinite number of primes $n-1$, which contradicts the assumption that $n-1$ does not divide $P(n)$ (we used the pigeonhole principle). Hence, $n-1 \mid P(n)$ for all $n-1$ prime greater than 2000, i.e., for an infinite number of numbers. We deduce that $n-1$ divides $P(n)$ for all integers $n$. Writing $P(n)=Q(n)(n-1)+r$, we see that $r$ is divisible by an infinite number of primes, so $r=0$ and $P(n)$ is divisible by $n-1$. We now take $R(n)=\frac{P(n)}{n-1}$, which is also a solution to the problem. Therefore, $P(n)=a(n-1)^{k}$ for some integer $k$.

We first show that $a= \pm 1$. Indeed, setting $n=a m$ with $m$ sufficiently large so that $a m \geqslant 2001$, we find $a \mid P(a k) \mid (a k)^{a k-1}-1$, which is a contradiction if $a$ is different from 1 and -1. Therefore, $a= \pm 1$.

We deduce that $P(n)$ is of the form $\pm(n-1)^{k}$. We will show that $k$ is 0, 1, or 2.

If $k=0$, we clearly have that $P(n) \mid n^{n-1}-1$ for all integers $n \geqslant 2001$. $P(n)= \pm 1$ is indeed a solution.

If $k=1$, we have $n^{n-1}-1=(n-1)\left(n^{n-2}+n^{n-3}+\ldots+n+1\right)$, which is clearly divisible by $\pm n-1$. $P(n)= \pm(n-1)$ is indeed a solution.

If $k=2$, we have $n^{n-2}+n^{n-3}+\ldots+n+1 \equiv 1+1+\ldots+1+1 \equiv n-1 \equiv 0(\bmod n-1)$.

Thus, $n^{n-1}-1=(n-1)\left(n^{n-2}+n^{n-3}+\ldots+n+1\right)$ is indeed divisible by $(n-1)^{2}$.

We will now show that $(n-1)^{3}$ does not always divide $n^{n-1}-1$, and thus $P(n)=$

![](https://cdn.mathpix.com/cropped/2024_05_10_346641170ac76390eef3g-375.jpg?height=55&width=1711&top_left_y=1663&top_left_x=178)
does not always divide $(a+1)^{a}-1$. Now, $(a+1)^{a}-1=a^{a}+a \cdot a^{a-1}+\binom{a}{2} \cdot a^{a-2}+\ldots+\binom{a}{2} \cdot a^{2}+a \cdot a+1-1=$ $(\cdots) a^{3}+\binom{a}{2} \cdot a^{2}+a^{2}$. We want to show that $a^{3}$ does not always divide $\binom{a}{2} \cdot a^{2}+a^{2}$, or equivalently, that $a$ does not always divide $\left(\frac{a(a-1)}{2}+1\right)$. Taking $a$ to be odd, $2 \mid a-1$, and thus $a \nmid \frac{a(a-1)}{2}+1$, which concludes the proof.