Let $p$ be a prime number. For every $n \in \mathbb N$, let
$A_{p,n}:=\{\deg P(X) : P(X)\in \mathbb Z[X]$ is monic and $p^n|P(m), \forall m \in \mathbb Z$ $\}$ .
As user abx notes below, $A_{p,n}$ is non-empty.
If we define $f(n,p):=\min A_{p,n}$, then how to show that $\lim _{n\to \infty}\dfrac {f(n,p)}{n}=p-1$ ?
Let $P$ be a monic polynomial of degree $d$, such that $P(\mathbb{Z})\subset p^n\mathbb{Z}$. Then $p^{-n}P$ takes integer values; as is well-known, this implies $p^{-n}P(t)=a_0\binom{t}{d}+a_1\binom{t}{d-1}+\ldots $ for some integer coefficients $a_i$. Since $P$ is monic we have $a_0p^n=d!$, that is, $p^n\mid d!$; conversely if this holds the polynomial $P=d!\binom{t}{d}$ satisfies $P(\mathbb{Z})\subset p^n\mathbb{Z}$. Thus $f(p,n)= \min \{d\ |\ n\leq v_p(d!) \} $, where $v_p$ is the $p$-adic valuation.
We have $v_p(d!)=\lfloor\frac{d}{p}\rfloor+\lfloor\frac{d}{p^2}\rfloor+\ldots $, from which one gets easily $v_p(d!)\leq \dfrac{d}{p-1} $, hence $n\leq \dfrac{f(p,n)}{p-1} $ or $\dfrac{f(p,n)}{n}\geq p-1 $. A slightly more subtle computation gives $v_p(d!)\geq \dfrac{d-p}{p-1}-\log_p(d) $, from which one gets, for any $\epsilon>0$, $\ \dfrac{f(p,n)}{n}\leq p-1+\epsilon\ $ for $n$ large enough, hence the result.
