# Polynomial that permutes residue classes

Prove that for any integers $d, e > 1$, the polynomial $f$ with integer coefficients permutes the residue classes modulo $p^d$ if and only if it permutes the residue classes modulo $p^e$ where $p$ is prime (that's it, $f(0),...,f(p^d-1)$ are distinct mod $p^d$ iff $f(0),...,f(p^e-1)$ are distinct mod $p^e$).

WLOG $e\ge d$. Then the "if" direction is trivial. For the "only if" direction, I'm able to show for $0\le q <p^{e-d},0\le r< p^d$,

$f(p^dq+r)\equiv f(r)+f'(r)p^dq+\frac{f''(r)}{2!}(p^dq)^2+...+\frac{f^{(u)}(r)}{u!}(p^dq)^u\pmod {p^e}$ where $u=\lfloor{\frac{e}{d}\rfloor}$

Therefore it suffices to prove $f'(r)+\frac{f''(r)}{2!}(p^dq)+...+\frac{f^{(u)}(r)}{u!}(p^dq)^{u-1}\not\equiv0\pmod{p^{e-d}}$, which I'm not sure how (for the case $e-d\ge2$). If $e-d=1$, then we have to show $f'(r)\not\equiv0\pmod{p}$, which is true since $f(x+p)\equiv f(x)+f'(x)p\pmod{p^2}$ for $0\le x<p$. By hypothesis $f(x+p)\not\equiv f(x)\pmod{p^d}$, so $f'(x)$ is nonzero mod $p$. Since $f'(x+p)\equiv f'(x)$, $f'(x)$ is nonzero mod $p$ for all integer $x$.

-

You already had all the right ideas. Now just use induction over $|e-d|$.