Let $p$ be a prime and $a, b$ natural numbers such that $1 \leq b \leq a$. I am trying to prove that $$\binom{ap}{bp} \equiv \binom{a}{b} \pmod p.$$
Furthermore, I have been tasked with proving that a stronger version of this holds: $$\binom{ap}{bp}\equiv \binom{a}{b} \pmod{p^2}.$$
I need an elementary proof of this (Lucas's theorem is out of the question).
I've been trying to prove the first inequality using the equivalence $(1 + x)^{ap} \equiv (1 + x)^p \pmod p,$ where $x$ is an integer. I've tried to expand $(1+x)^{ap}$ and $(1 + x)^p$ using the binomial theorem and then match coefficients, but I haven't been able to get the result doing this. How can I prove this first congruence (and the second one)?
Thanks.
Best Answer
Claim: $$\dbinom{pa}{pb} \equiv \dbinom{a}b \pmod {p^2}$$
Proof:
$$(x+1)^{pa} = (x^p+1+pQ(x))^a$$ for some polynomial $Q$ by the binomial theorem. Then we have $$(x+1)^{pa} = (x^p+1)^a+a(x^p+1)^{a-1}pQ(x)+p^2f(x)$$ for a polynomial $f$.
This gives
$$(x+1)^{pa} \equiv (x^p+1)^a+a(x^p+1)^{a-1}+pQ(x) \pmod {p^2}.$$
Since $pQ(x) = (x+1)^p-1-x^p$, substitution gives
$$(x+1)^{pa} \equiv (x^p+1)^a+a(x^p+1)^{a-1}((x+1)^p-1-x^p)$$ $$ \equiv (x^p+1)^a+a(x^p+1)^{a-1}(x+1)^p-a(x^p+1)^{a-1}-x^pa(x^p+1)^{a-1}. \pmod {p^2}$$
Now by a simple counting argument, the coefficient of $x^{pb} \pmod {p^2}$ termwise is
$$\dbinom{a}b + a\left(\dbinom{a-1}b+\dbinom{a-1}{b-1}\right)-a\dbinom{a-1}{b}-a \dbinom{a-1}{b-1} \equiv \dbinom{a}b \pmod {p^2}$$ as desired.
It's pretty cool to see that the terms conspire like that at the end. I think a similar proof would also work for $p^3$. I remember seeing a combinatorial proof for the $p^3$ case somewhere... I can possibly retrieve it if anyone wants me to.