Let $p$ be an odd prime and $n \geq 2$. 


(1) Does there exist an integer-coefficient polynomial $f$ such that $f(x) = x - (x \bmod p)$ for all $x \in \mathbb{Z}/p^n \mathbb{Z}$? The polynomial effectively removes the first base-$p$ digit of $x$. For example, if $n = 2$, then the defining property is $f(a+bp) = bp$.


(2) If so, then how can we find such a polynomial with lowest possible degree? How does this lowest degree change with $n$?


UPDATE: I am super amazed. Because the reason I asked the question is because by trial and error I have an algorithm to construct polynomials of degree $(n-1)(p-1) + 1$ that works for small $n$, but can't quite finish the proof by induction to all $n$. This has been bugging me for past few days. Seeing the answers confirm with my heuristic is just thrilling! 


SECOND UPDATE: Can we generalize this to functions that removes the lower $k$-digits, i.e., $f(x) = x - (x \mod p^k)$ for all $x \in \mathbb{Z}/p^n \mathbb{Z}$?


Thank you all for your nice answers! 



lowest degree of polynomial that removes the first digit of an integer in base p
Yes, this can be done, and the bound for the degree given by Neil Strickland (that is, $(n-1)\cdot(p-1)+1$ holds. 


Let $F\_A(x)$ be the formal sum in binomial coefficients
$$ F\_A(x):=\sum\_{j=0}^\infty (-1)^j \begin{pmatrix}A-1+j\\j\end{pmatrix}\begin{pmatrix}x\\A+j\end{pmatrix}.$$


Then $F\_A(x)$ converges on every integer, and for $M\in \mathbb Z$ we have 
$$
F\_A(M)=\begin{cases}1 & M\geq A\\ 0 & \text{otherwise.}\end{cases}
$$
The 'otherwise' part of the claim is easy. The rest follows by noticing that $F\_A(M)$ is the same as coefficient of $X^{M-A}$ found by taking the product of the Taylor series of $(1+X)^{-A}$ and the polynomial $(1+X)^M$. The result is of course $1$.


Let $$G(x):= p\cdot \sum\_{j=1}^\infty F\_{j\cdot p}(x)=\sum\_{m=0}^\infty a(m)\begin{pmatrix}x\\m\end{pmatrix},$$ where 
$$a(m):= p\sum\_{k=0}^\infty (-1)^{m-kp} \begin{pmatrix}m-1\\m-kp\end{pmatrix}.$$
Then for $M$ a positive integer, we have $0\leq M-G(M)<p$ and $M-G(M)\equiv M \pmod{p}.$ 


We then define $\tilde G(x)$ to be the same sum, truncated at $m=(n-1)(p-1)+1.$ I claim this polynomial has $p$-integral coefficients, and satisfies the desired properties, and so reduces to a polynomial with integer coefficients satisfying the properties.


Using the identity $$(-1)^k\begin{pmatrix}n\\k\end{pmatrix}=\begin{pmatrix}k-n-1\\k\end{pmatrix},$$ we find that $a(m)$ is the coefficient of $X^m$ in the Taylor expansion of $$ p\sum\_{k=0}^\infty \left(\frac{X}{1+X}\right)^{rp}=p\frac{(1+X)^p}{(1+X)^p-X^p}.$$ The denominator on the right can be written as $1+B(X)$ where $B(X)$ is divisible by $px$ and has degree $p-1.$ From here it is not hard to see that $a(m)\equiv 0 \pmod{p^n}$ when ever $m>(n-1)(p-1)+1$. Thus, truncating the sum as described above does not change the valuer, mod $p^n$. 


We now just need to show that $\tilde G$ can be expanded in a polynomial with $p$-integral coefficients. Each binomial coefficient $\begin{pmatrix}x\\m\end{pmatrix}$ introduces a denominator of $m!$, which has $p$-adic valuation bounded by $$v\_p(m!)<\frac{m}{p-1}$$. But as we already saw, $v\_p(a(m))>\frac{m}{p-1}$ so the coefficient of $\tilde G(x)$ are indeed $p$-integral.


