Prove that $\binom{p^k}{pn}\equiv\binom{p^{k-1}}n\pmod{p^{2k+1}}.$ Let $k$ be a positive integer, $p>3$ a prime,
and $n$ an integer with $0\le n\le p^{k-1}$. Prove that
$\binom{p^k}{pn}\equiv\binom{p^{k-1}}n\pmod{p^{2k+1}}.$
This is CMO 2019 P2
$\binom{p^k}{pn}=\frac{p^k!}{pn!\cdot {(p^k-pn)}!}$
This problem is giving me Lucas vibes. We have $\binom{pa}{pb}\equiv \binom{a}{b}\mod p.$
 A: If we allow ourselves to start with the strong result from p-adic considerations; the Kazandzidis congruence for $p>3$,
$$\binom{pn}{pk} \equiv \binom{n}{k} \mod p^3nk(n-k) \binom{n}{k} \mathbb{Z}_p$$
Here $\mathbb{Z}_p$ is the p-adic integers.
We can make the appropriate substitutions for our problem to get to,
$$\binom{p^k}{pn} \equiv \binom{p^{k-1}}{n} \mod p^{k+2}n(p^{k-1}-n) \binom{p^{k-1}}{n} \mathbb{Z}_p$$
On its own this is not enough, we need to refine this by focusing on the power of $p$ dividing the binomial term. I think there's a better way of doing this than how I'm about to do it, but this works. We can look at it through Legendre's formula/Kummer's theorem which says the p-adic valuation of the binomial coefficient is related to sums of digits of some numbers when written in base $p$,
$$v_p\left(\binom{a}{b}\right) = \frac{s_p(b)+s_p(a-b)-s_p(a)}{p-1}$$
In our case,
$$v_p\left(\binom{p^{k-1}}{n}\right) = \frac{s_p(n)+s_p(p^{k-1}-n)-s_p(p^{k-1})}{p-1}$$
We can do a few simplifications, immediately $s_p(p^{k-1})=1$ and we can use the fact that $p^{k-1}-1$ has exactly $k-1$ digits that are $p-1$ to rewrite: $s_p(p^{k-1}-n) = s_p(p^{k-1}-1-(n-1)) = (p-1)(k-1) - s_p(n-1)$,
$$v_p\left(\binom{p^{k-1}}{n}\right) = \frac{s_p(n)+(p-1)(k-1) - s_p(n-1)-1}{p-1}$$
$$v_p\left(\binom{p^{k-1}}{n}\right) = k-1 + \frac{s_p(n) - s_p(n-1)-1}{p-1}$$
The last term can be simplified with Legendre's formula in reverse,
$$v_p\left(\binom{p^{k-1}}{n}\right) = k-1 + v_p((n-1)!)-v_p(n!)$$
$$v_p\left(\binom{p^{k-1}}{n}\right) = k-1 - v_p(n)$$
This is much more promising, let's put this back in our formula and amend it by putting $n=p^{v_p(n)}m$ (here $v_p(m)=0$) everywhere along with $\binom{p^{k-1}}{n} = p^{k-1-v_p(n)}u$
$$\binom{p^k}{pn} \equiv \binom{p^{k-1}}{n} \mod p^{k+2}p^{v_p(n)}m(p^{k-1}-p^{v_p(n)}m) p^{k-1-v_p(n)}u \mathbb{Z}_p$$
$$\binom{p^k}{pn} \equiv \binom{p^{k-1}}{n} \mod p^{2k+1}(p^{k-1}-p^{v_p(n)}m)\mathbb{Z}_p$$
The $m$ and $u$ terms are units in $\mathbb{Z}_p$ and so are safely removed. What we have here is actually a bit more general than the problem asks, so we can discard the extra $p^{k-1}-p^{v_p(n)}m$ term if we like, which gives us a higher power of $p$ that this congruence holds in the case that $n$ is divisible by a power of $p$.
