# 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.

• A very useful formula: If $a=\sum a_ip^i$ and $b=\sum b_ip^i$ then $\displaystyle \binom{a}{b} \equiv \prod \binom{a_i}{b_i}\pmod p$. This can be proved by looking at $x^b=x^{\sum b_ip^i}$ coefficient in $(1+x)^a=(1+x)^{\sum a_i p^i}$. – Quang Hoang Jul 29 '14 at 4:31
• Isn't that Lucas's Theorem? I'm hoping for a proof that's more elementary, if possible. – James Pirlman Jul 29 '14 at 4:35
• Ah, I didn't know what it called before this. Wasn't you trying to proof Lucas' Theorem (by expanding $(1+x)^{ap}$)? – Quang Hoang Jul 29 '14 at 4:35
• – lab bhattacharjee Jul 29 '14 at 5:27
• I proved the stronger $\pmod{p^3}$ claim here: math.stackexchange.com/questions/850724/binomial-congruence – Jack D'Aurizio Aug 4 '14 at 9:46

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.