Serbian Mathematical Olympiad

Denote $P(x)=x^{n}+x^{n-1}+\cdots+1$ and $Q(x)=x^{n!}+\cdots+x^{1!}+1$; let $Q(x)=C(x) P(x)+R(x)$, where $C$ and $R$ are polynomials with integer coefficients and $\operatorname{deg} R<\operatorname{deg} P$. By the condition of the problem $P(a) \mid Q(a)$, and hence $P(a) \mid R(a)$, for infinitely many integers $a$. Since for sufficiently large $a$ we have $|R(a)|<|P(a)|$, it must be that $R(a)=0$; therefore, $R(x)$ has infinitely many zeros, so $R(x) \equiv 0$ and $P(x) \mid Q(x)$.

Lemma. Let $k_{0}, k_{1}, \ldots, k_{n} \in \mathbb{N}_{0}$. The polynomial $P(x)=x^{n}+x^{n-1}+\cdots+1$ divides $Q(x)=x^{k_{n}}+\cdots+x^{k_{1}}+x^{k_{0}}$ if and only if $\left\{k_{0}, k_{1}, \ldots, k_{n}\right\}$ is a complete system of residues modulo $n+1$.

Proof. Let $r_{i}$ be the remainder when $k_{i}$ is divided by $n+1$. Since $x^{n+1}-1$ divides $x^{k_{i}}-x^{r_{i}}$ for all $i$, it follows that $P(x)=\frac{x^{n+1}-1}{x-1}$ divides $Q(x)-Q_{1}(x)$, where $Q_{1}(x)=x^{r_{0}}+x^{r_{1}}+\cdots+x^{r_{n}}$ and moreover $\operatorname{deg} Q_{1} \leqslant n$. If $P(x) \mid Q(x)$, then $P(x) \mid Q_{1}(x)$, i.e. $Q_{1}(x)=c P(x)$ for some constant $c$, and this holds if and only if $c=1$ and $\left\{r_{0}, r_{1}, \ldots, r_{n}\right\}=\{0,1, \ldots, n\}$.

From the lemma it follows that the required numbers $n$ are those for which $\{0,1!, \ldots, n!\}$ is a complete system of residues modulo $n+1$.

If $n>3$ and $n+1$ is a composite number, then $n!\equiv 0(\bmod n+1)$, so the condition is not satisfied. If $n+1=p>3$ is prime, by Wilson's theorem $(p-1)!\equiv-1(\bmod p)$, from which $(p-2)!\equiv 1=1!(\bmod p)$, and again the condition is not satisfied. The remaining cases are $n \leqslant 3$; direct verification shows that $n=1$ and $n=2$ satisfy the conditions.

Second solution. We will prove a stronger statement: if $A=a^{n}+\cdots+a+1$ divides $a^{k_{n}}+\cdots+a^{k_{1}}+a^{k_{0}}$ for some $a \in \mathbb{N} \backslash\{1\}$, then $\left\{k_{0}, k_{1}, \ldots, k_{n}\right\}$ is a complete system of residues modulo $n+1$.

Let $A \mid B=a^{k_{n}}+\cdots+a^{k_{1}}+a^{k_{0}}$. Denote by $r_{i, j}$ the remainder when $k_{i}+j$ is divided by $n+1$, and consider the numbers $B_{j}=a^{r_{n, j}}+\cdots+a^{r_{1, j}}+a^{r_{0, j}}$. Then $B_{j} \equiv a^{j} B(\bmod A)$, from which it follows that $A \mid B_{j}$ for $j=0,1, \ldots, n$. On the other hand, $B_{0}+B_{1}+\cdots+B_{n}=\sum_{j} a^{r_{n, j}}+\cdots+\sum_{j} a^{r_{1, j}}+\sum_{j} a^{r_{0, j}}=(n+1) A$, so since $B_{j}>0$, it must be that $B_{j}=A$ for all $j$. From the inequality $A<2 a^{n}$ we conclude that, for every $j$, at most one of the remainders $r_{i, j}$ is equal to $n$. But if $k_{i} \equiv k_{i^{\prime}} \equiv n-j(\bmod n+1)$, then $r_{i, j}=r_{i^{\prime}, j}=n$, which is impossible. Therefore, $k_{0}, k_{1}, \ldots, k_{n}$ are pairwise distinct modulo $n+1$, which was to be proved.

From the lemma it follows that the required numbers $n$ are those for which $\{0,1!, \ldots, n!\}$ is a complete system of residues modulo $n+1$.
If $n>3$ and $n+1$ is a composite number, then $n!\equiv 0(\bmod n+1)$, so the condition is not satisfied. If $n+1=p>3$ is prime, by Wilson's theorem $(p-1)!\equiv-1(\bmod p)$, from which $(p-2)!\equiv 1=1!(\bmod p)$, and again the condition is not satisfied. The remaining cases are $n \leqslant 3$; direct verification shows that $n=1$ and $n=2$ satisfy the conditions.