Binomial Congruence Modulo a Prime

Question

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.

Answer 1

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.

Answer 2

A standard combinatorial proof goes like this. Arrange $pa$ elements in $a$ rows of $p$ elements each. We want to mark $pb$ elements out of those, for which there are $\binom{pa}{pb}$ ways.

Case $1$. We mark $b$ entire rows of $p$ elements each. This accounts for $\binom{a}{b}$ choices.

Case $2$. The $pb$ marked elements don't fill at least $1$ of the rows in which they are located. Moreover, because the total number of chosen elements is divisible by $p$, there cannot be exactly $1$ such row, so there is at least $2$ such rows. Choose any row in which some, but not all, of the elements are marked. Rotate the marks in such a row as if on a cylinder. In other words, if marked elements are in columns $c_1<\dots<c_k$, with $1\le c_1\le c_k\le p$ and $1\le k\le p-1$, then consider choices $(c_1+i\!\!\!\mod\!\!p,\dots,c_k+i\!\!\!\mod\!\!p)$ for $i=0,1,\dots,p-1$. Because $p$ is prime and $0<k<p$, the rotation period is $p$. Declare two markings equivalent if one can be obtained from the other by mark rotation as described above. Then the number of elements in each equivalence class in Case $2$ is divisible by $p^2$, since at least $2$ rows can be rotated independently with period $p$. Thus, the number of markings in Case $2$ is divisible by $p^2$.