# Binomial Congruence Modulo a Prime

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.

#### Solutions Collecting From Web of "Binomial Congruence Modulo a Prime"

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.

A short proof is given here. But it uses the language of groups acting on sets, you may not be comfortable with that.