Skip to main content
11 of 12
added 35 characters in body
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79

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} \bmod 2 \equiv 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.
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79