
N1. Determine all polynomials $f$ with integer coefficients such that $f(p)$ is a divisor of $2^{p}-2$ for every odd prime $p$.

ITALY


Solution 1. The required polynomials are $\pm 1, \pm 2, \pm 3, \pm 6, \pm X, \pm 2 X$. It is readily checked that all these polynomials satisfy the condition in the statement.

Now let $f$ be a polynomial satisfying the required condition, and assume first that $f(0) \neq 0$. Let $S$ be the set of those primes $p$ such that $p \mid f(p)$. Since $f(0) \neq 0$, the set $S$ is finite, so $p \nmid f(p)$ for all but finitely many primes $p$. Let $p$ be a large enough such prime, and suppose, if possible, that $f(p)$ is divisible by some prime $q>3$. Refer to the Chinese remainder theorem to find an integer $R$ with $R \equiv p(\bmod q)$ and $R \equiv-1(\bmod q-1)$, and notice that $R$ is coprime to $q(q-1)$. Now, by Dirichlet's theorem on primes in arithmetic sequences of integers, there exists a prime $r \neq p$ such that $r \equiv R(\bmod q(q-1))$, that is, $r \equiv p(\bmod q)$ and $r \equiv-1(\bmod q-1)$.

Clearly, $f(r) \equiv f(p) \equiv 0(\bmod q)$, so $q|f(r)| 2\left(2^{r}-2\right)=2^{r+1}-4$. Since $q>2$, the condition $r+1 \equiv 0(\bmod q-1)$ and Fermat's little theorem imply $2^{r+1} \equiv 1(\bmod q)$, hence $0 \equiv 2^{r+1}-4 \equiv 1-4 \equiv-3(\bmod q)$; that is, $q=3$, contradicting the choice $q>3$. Consequently, for every large enough prime $p$, the only primes that may divide $f(p)$ are 2 and 3 .

On the other hand, $f(p) \mid 2^{p}-2$, and $4 \nmid 2^{p}-2$, so $v_{2}(f(p)) \leq 1$; moreover, if $p \equiv 5(\bmod 6)$, then $2^{p}-2 \equiv 2^{5}-2 \equiv 30 \equiv 3(\bmod 9)$, so $v_{3}(f(p)) \leq 1$ for any such $p$. Consequently, $|f(p)| \leq 6$ for every large prime $p \equiv 5(\bmod 6)$, so $f$ is constant. Since this constant divides $2^{3}-2=6$, it is one of $\pm 1, \pm 2, \pm 3, \pm 6$.

Finally, we deal with the case $f(0)=0$. Write $f=X^{m} \cdot g$ for some positive integer $m$ and some polynomial $g$ with integer coefficients such that $g(0) \neq 0$. Since $g$ also satisfies the condition in the statement, it is one of $\pm 1, \pm 2, \pm 3, \pm 6$. The condition $f(3) \mid 2^{3}-2=6$ then forces $m=1$ and $g= \pm 1$ or $\pm 2$, so $f= \pm X$ or $\pm 2 X$.
