Nemotron-IMO-Bench 2026 N43

Let $f\in \mathbf{Z}[X]$ have degree $d$ and such that for some prime $p$ the number of pairwise distinct remainders mod $p$ of the numbers $f(1),\ldots, f(p)$ is $k\in (1,p)$. Prove that $$\frac{p-1}{d}\leq k-1\leq (p-1)(1-\frac{1}{d}).$$