Binomial coefficient congruence modulo $p^n$

Question

I am interested in the following congruence $$\binom{ap^n}{bp^n}\equiv \binom{a}{b}\pmod{p^n}$$ I am aware that by some reference in a book the above it should actually hold modulo $p^{3n}$; the reference in question is Zieve (1999) but could not find any trace of the paper. I am also aware of the various generalizations of Lucas's theorem, but I do not see how it follows directly from one of them. By standard tricks you can reduce the above to $$\binom{ap^n-1}{p^n-1}\equiv 1 \pmod{p^n}.$$

Answer 1

This is false in general.

To show this, I will use the congruence $$ \binom{p^k a}{p^k b} \equiv \binom{p^{k-1} a}{p^{k-1}b} \bmod p^{3k}$$ for $p\ge 5$ and $k \ge 1$.

This is originally due to Ljunggren and Jacobsthal in "On the divisibility of the difference between two binomial coefficients" in Skand. Mat.-Kongr., Trondheim 1949, 42-54 (1952). The case $k=1$ was established in the 19th century by Wolstenholme, with earlier works (with smaller exponents) by Cabbage and Lucas. See also Meštrović's survey mentioned in Ira Gessel's answer.

Let us consider the case $a=2$, $b=1$, $n=4$ of your congruence. You claim $$\binom{2p^4}{p^4} \equiv \binom{2}{1} \bmod p^4.$$ Here is why it fails. By Ljunggren--Jacobsthal, $$\binom{2p^4}{p^4} \equiv \binom{2p^3}{p^3} \bmod p^{12},$$ $$\binom{2p^3}{p^3} \equiv \binom{2p^2}{p^2} \bmod p^{9},$$ $$\binom{2p^2}{p^2} \equiv \binom{2p}{p} \bmod p^{6}.$$ In particular, we do know that $$\binom{2p^4}{p^4} \equiv \binom{2p}{p} \bmod p^4.$$ Your congruence then implies that $$\binom{2p}{p} \equiv 2 \bmod p^4.$$ Primes that satisfy this have a name: they are called Wolstenholme primes. The only such primes up to $10^9$ are 16843 and 2124679... One can show that $p$ is such a prime iff $p$ divides the numerator of the Bernoulli number $B_{p-3}$.

The proofs of Ljunggren--Jacobsthal suggest that for any given $a,b$, your congruence fails if $n > 3+\nu_p(\binom{a}{b}ab(a-b))$ where $\nu_p$ is the $p$-adic valuation.

---

For $n\le 3$ your congruence is true and directly follows from Ljunggren-Jacobsthal. Indeed, applying L-J with $k=1,2,3$ we have, in particular, that $$\binom{ap^3}{bp^3} \equiv \binom{ap^2}{bp^2} \equiv \binom{ap}{bp} \equiv \binom{a}{b} \bmod p^{3}.$$

---

A more refined version of Ljunggren--Jacobsthal was proved by G. S. Kazandzidis: $$ \binom{ap}{bp} \equiv \binom{a}{b} \bmod p^{3+\delta}$$ where $\delta=\nu_p(ab(a-b)\binom{a}{b})$. This allows you to extend the range of validity $n \le 3$ if one of $a$, $b$, $a-b$ or $\binom{a}{b}$ is divisible by $p$.

This result (and variations) is proved in:

• "On a congruence and on a practical method for finding the highest power of a prime p which divides the binomial coefficient (AB)", Bull. Soc. Math. Grèce, N. Sér. 6, No. 2, 358-360 (1965).
• "Congruences on the binomial coefficients", Bull. Soc. Math. Grèce, N. Ser. 9, No. 1, 1-12 (1968).
• "On congruences in number-theory", Bull. Soc. Math. Grèce, N. Sér. 10, No. 1, 35-40 (1969).

All the mentioned papers are elementary. The modern treatment is a bit less so, but is more illuminating. Indeed, $p$-adic analysis can lead to a proof. See Chapter 7 of Alain M. Robert's book "A course in p-adic analysis" (GTM 198, Springer, 2000). The proof given there is based on the material in the paper "The Kazandzidis supercongruences. A simple proof and an application", Rend. Semin. Mat. Univ. Padova 94, 235-243 (1995), by Alain M. Robert and Maxime Zuber.

Some remarks:

• The congruence $\binom{ap^k}{bp^k} \equiv \binom{ap^{k-1}}{bp^{k-1}} \bmod p^{2k}$ has a combinatorial proof (as opposed to algebraic proofs mod $p^{3n}$). A reference for a combinatorial proof when the modulus is $p^n$ is Gian-Carlo Rota and Bruce Sagan's paper "Congruences derived from group action", Eur. J. Comb. 1, 67-76 (1980). I am not sure if this is the earliest reference of this kind of argument, though.
• There are various $q$-analogues of these $p$-adic congruences.
• Some of the above papers include also the cases $p=2$ and $p=3$ for which the exponent of $p$ in the modulus is slightly smaller.

Answer 2

A comprehensive account of these congruences can be found in Romeo Meštrović,Wolstenholme's theorem: Its Generalizations and Extensions in the last hundred and fifty years (1862–2012), https://doi.org/10.48550/arXiv.1111.3057.