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$. 



$p | f(x)$ if and only if $p^k | x$.
Your construction is optimal, that is, the degree of $f$ is always at least $2p^{k-1}-1$. Note that if $m,x$ have $p$-base expansions $m=\sum\_{i}m\_i p^i$, $x=\sum\_{i}x\_i p^i$, we have $\binom{x}{m}\equiv \prod \binom{x\_i}{m\_i} \pmod p$ by [Lucas' theorem](https://en.wikipedia.org/wiki/Lucas%27_theorem), and any integer-valued polynomial is an integer linear combinations of binomials $\binom{x}{m}$ (whose result is it, by the way?). So your question is essentially about polynomials in $k$ variables $x\_0,\dots,x\_{k-1}$ over $\mathbb{F}\_p$, which are reduced (have degree at most $p-1$ in each variable). Assume that degree of $f$ is strictly less than $2p^{k-1}-1$. It means that the corresponding polynomial $F\in \mathbb{F}\_p[x\_0,\dots,x\_{k-1}]$ is at most linear in $x\_{k-1}$ and its coefficient of $x\_{k-1}x\_0^{p-1}\dots x\_{k-2}^{p-1}$ equals 0. Denote $F=g(x\_0,\dots,x\_{k-2})+x\_{k-1}h(x\_0,\dots,x\_{k-2})$ and write $y=(x\_0,\dots,x\_{k-2})$. We have $g(0)=0$, $g(y)\ne 0$ for $y\ne 0$, $h(0)\ne 0$, $h(y)=0$ for $y\ne 0$ (else we may set $x\_{k-1}=-g(y)/h(y)$ and find another root of $F$.) But then we may [reconstruct](https://mathoverflow.net/questions/214927/important-formulas-in-combinatorics/214930#214930) the coefficient of $x\_0^{p-1}\dots x\_{k-2}^{p-1}$ in the polynomial $h(x\_0,\dots,x\_{k-2})$, and it is non-zero: the sum contains unique non-negative summand (I guess, it is a partial case of Alon-Füredi theorem). A contradiction. 


