Given a prime number $p$ and a positive integer $k$. Consider integer-valued polynomials $f$ satisfying the property that $p | f(x) \Leftrightarrow p^k | x$.

**Question.** What is the smallest degree of such $f$?

I can construct such an $f_k$ with degree $2p^{k-1} - 1$. The idea is to use induction with $f_1 = x$ and $$f_{k+1} = f_k + \sum_{j = 0}^{p^k-1} (-1)^{j} \binom{x}{p^k+j}.$$ Using Lucas' theorem, it can be shown that the sum $\sum_{j = 0}^{p^k-1} (-1)^{j} \binom{x}{p^k+j}$ is 0 $mod~p$ when $p^k \nmid x$, and it is $r~mod~p$ when $p^k | x$, where $r$ is defined to be the residue of $\frac{x}{p^k}$ $mod~p$. Thus when $p^k \nmid x$, $f_{k+1}(x) \equiv f_{k}(x)$ is not divisible by $p$ by induction hypothesis. And when $p^k \mid x$, $f_{k+1}(x) \equiv f_k(x) + r \equiv r~(mod~p)$. It is divisible by $p$ precisely when $p | r$, or $p^{k+1} | x$.

I can also show this construction is optimal for $k = 1, 2$. The case $k = 1$ is trivial. For $k = 2$, write any such $f$ as $\frac{g}{p^l}$ where $g$ is a primitive polynomial with integer coefficients and $l \in\mathbb{Z}$. Ignoring other possible factors in the numerator/denominator is without loss. The condition implies $l$ cannot be negative, and $l$ cannot be zero because then we deduce from $p|g(0)$ that $p|g(p) = f(p)$. Moreover, if $l \geq 2$ then the degree of $f$ must be $2p$, due to Polya's result that $d!f(x) \in Z[x]$. Thus we can assume $l = 1$. By condition we have $p| g(x)$ for every integer $x$ but $p^2| g(x)$ only when $p^2 | x$. Hensel's lemma then yields $p | g'(x)$ whenever $p \nmid x$. Therefore $g$ has double roots at every $x \in F_p^*$ and at least one root at $x = 0$, suggesting its degree must at least be $2p-1$.

I'm not sure how far this method can be extended to larger $k$, although I do suspect $2p^{k-1}-1$ is the right answer. In general I can only show $d \geq \frac{p^k-1}{p-1}$ by noting that $1-f^{p-1}$ vanishes at $x = 1, 2, \dots, p^{k}-1$ but not at $x = 0$. This implies for $p = 2$ the answer is indeed $2^k-1$.