A remainder read two digits at a time

Lucas’ theorem says that the remainder of a binomial coefficient on division by a prime $p$ can be read off the base-$p$ digits one column at a time: write $n$ and $k$ in base $p$, take the small coefficient $\binom{n_i}{k_i}$ in each column, and multiply. Kummer’s theorem answers a different question exactly — how many times $p$ divides the coefficient — by counting carries. Neither says what the coefficient leaves on division by $p^2$.

The natural guess is that the digit product keeps working one power higher. It does not, and the failure is not rare.

Modulo a prime power a binomial coefficient is still decided by its digits — but by the digits read in overlapping windows, after the prime has been taken out, and with a sign the carries decide. That is Granville’s theorem, and the reason it takes that shape is short enough to give in full.

Where the one-digit proof gives way #

Lucas’ theorem has a two-line proof, and the place it stops is exactly one power of $p$ up.

Write $n = n_0 + n_1 p + n_2 p^2 + \cdots$ in base $p$. Then $(1+x)^n$ is the product of $(1+x)^{n_i p^i}$ over the digits. Modulo $p$, raising to the $p$-th power is additive, so $(1+x)^p \equiv 1 + x^p$, and each factor becomes $(1+x^{p^i})^{n_i}$. The powers $x^{p^i}$ live in separate columns, so the coefficient of $x^k$ in the product is the product of one small coefficient per column — which is the theorem.

The step that needs care is $(1+x)^p \equiv 1 + x^p$. The coefficients thrown away are $\binom{p}{1}, \dots, \binom{p}{p-1}$, and each of them is divisible by $p$ exactly once. Modulo $p$ they vanish. Modulo $p^2$ they survive: $(1+x)^2 = 1 + 2x + x^2$, and the $2x$ is nought on a dial of two and not on a dial of four.

So modulo $p^2$ the columns are no longer separate. The surviving middle terms carry a contribution from one digit into its neighbour, and a rule that looks at one column at a time cannot see it. What that suggests, and what turns out to be true, is a rule that looks at two neighbouring columns at a time.

A remainder that needs two digits #

Modulo 4 the failure has a particularly simple form, because in binary every small coefficient is $\binom{1}{1}$, $\binom{1}{0}$ or $\binom{0}{0}$, and all three are 1. The digit product for an odd entry is therefore always 1. An odd entry is 1 or 3 modulo 4, so the digit product is wrong at exactly the odd entries that leave 3 — the deep-coloured cells of the first figure, and the dots are on precisely those.

Which odd entries leave 3 is itself a statement about digits, and it is a statement about pairs. When $\binom{n}{k}$ is odd, the ones of $k$ sit under ones of $n$, and $n - k$ takes the rest. Look at every place where $n$ has two ones side by side. Either $k$ takes both of them, or $n - k$ takes both, or they are split, one each. The entry leaves 3 on division by 4 exactly when an odd number of those adjacent pairs are split. The first figure checks that rule at every one of its 243 odd entries.

$\binom{13}{4} = 715$ is an example. Thirteen in binary is $1101$, with one adjacent pair of ones at the top; four is $0100$ and nine is $1001$, so four takes the lower one of the pair and nine the upper. One split pair, and $715 = 4 \times 178 + 3$. The digit product has no way to know that, because each column on its own looks the same whether the pair is split or not.

The digits come in windows #

The table in that figure is the general rule at work. Each row reads a window of two consecutive digits — of $n$, of $k$ and of $n - k$ — starting at a given place, and the windows overlap: the window starting at the second digit shares a digit with the one starting at the first.

For each window the rule takes the three numbers the windows spell, forms their factorials with every multiple of $p$ left out — written $(m!)_p$ — and divides the first by the product of the other two, modulo $p^2$. In $\binom{13}{4}$ the window from the third digit reads $11$, $01$ and $10$: three, one and two. Leaving out the even numbers, $(3!)_2 = 1 \times 3 = 3$, $(1!)_2 = 1$ and $(2!)_2 = 1$, so the ratio is 3. Every other window gives 1, the product is 3, and that is the remainder.

The rule in general, for the prime power $p^q$, is Andrew Granville’s theorem of 1997. Read windows of $q$ digits. Take the product over all windows of the ratio of $p$-free factorials. Multiply by $-1$ once for every carry out of the $q$-th column or any column above it, when $k$ and $n-k$ are added in base $p$ — except modulo 8 and the higher powers of two, where the sign is dropped. The result is the binomial coefficient with every factor of $p$ removed, modulo $p^q$. With $q = 1$ every window is a single digit, and when nothing carries the windows’ ratios are the small coefficients $\binom{n_i}{k_i}$ and the rule is Lucas’ theorem; when something does carry, it says what Lucas’ theorem cannot, namely what the coefficient leaves once its $p$s are gone.

Why a whole run of numbers counts only as a sign #

The proof has two steps, and the second is where the windows and the sign come from.

First, take the prime out of each factorial. Among $1, 2, \dots, m$ the multiples of $p$ are $p, 2p, \dots, \lfloor m/p \rfloor p$, whose product is $p^{\lfloor m/p \rfloor}$ times $\lfloor m/p \rfloor !$. So

$$m! = p^{\lfloor m/p\rfloor} \cdot \lfloor m/p\rfloor! \cdot (m!)_p,$$

and applying the same thing to $\lfloor m/p \rfloor !$, and again, writes $m!$ as a power of $p$ times the product of $(\lfloor m/p^j \rfloor !)_p$ over every $j$. Doing that to $n!$, $k!$ and $(n-k)!$ gives $\binom{n}{k}$ as a power of $p$ — Kummer’s count of carries — times a ratio of $p$-free factorials, one ratio per place $j$. That identity is exact, in whole numbers, with no modulus anywhere.

Second, reduce each $p$-free factorial modulo $p^q$. A run of $p^q$ consecutive numbers contains one number from every remainder class, so the product of its members that $p$ does not divide is, modulo $p^q$, the product of every unit on the dial of $p^q$. By the extension of Wilson’s theorem that product is $-1$ — for every odd prime power and for 4, with one family of exceptions that the next section is about. So $(m!)_p$ modulo $p^q$ depends only on the last $q$ digits of $m$, apart from a factor of $-1$ for every complete run — and those last $q$ digits of $\lfloor m/p^j \rfloor$ are exactly the window starting at place $j$.

The $-1$s have to be counted. For each place, the numbers of complete runs in $n$, $k$ and $n - k$ differ by one exactly when a carry crosses into the column where the runs are counted, so the signs that do not cancel number one per carry out of the $q$-th column or higher. That is the whole of the theorem. The windows are what a modulus of $p^q$ can remember of a factorial; the sign is what it cannot.

The exception that proves where the sign comes from #

The product of the units modulo $p^q$ is $-1$ for every odd prime power and for 4. It is not $-1$ modulo 8: the units are 1, 3, 5 and 7, and $1 \times 3 \times 5 \times 7 = 105$, which leaves 1.

The reason is the proof of Wilson’s theorem itself. Pair every unit with its inverse; the pairs multiply to 1, and what is left is the product of the units that are their own inverses. Modulo a prime there are two of them, 1 and $-1$, and the product is $-1$. Modulo 8 there are four — every unit squares to 1, since $3^2 = 9$, $5^2 = 25$ and $7^2 = 49$ all leave 1 — and their product is $+1$.

That happens because the units modulo 8 are not all powers of one of them: no unit has order four, so the group is not a cycle, and a cycle is what forces a single element of order two. Every odd prime power has a cycle of units, and so does 4; no higher power of 2 does. So Granville’s rule carries its sign for every prime power except $2^q$ with $q \ge 3$, where the sign is dropped — and the exception is not a patch on the theorem but a fact about which dials have a primitive root, arriving in a question about Pascal’s triangle.

Taking the prime out first #

When the coefficient is divisible by $p$ the rule describes what is left after the $p$s are removed, and the figure below takes the pair the essay on carries used, in base five.

The table reads the windows $00$, $40$, $04$ of one hundred, $22$, $12$, $01$ of thirty-seven and $23$, $22$, $02$ of sixty-three — each window sliding one digit along from the last. The product of the ratios is 21 modulo 25, the sign flips it to $-21$, which is 4, and the figure checks that against the coefficient itself: $\binom{100}{37}$ is $5^2 \times 136{,}801{,}181{,}899{,}757{,}525{,}756{,}109{,}504$, and the second factor does leave 4.

Two facts come out of that, and neither is visible from Lucas’ theorem or Kummer’s alone. The coefficient’s remainder modulo 25 is nought, which says nothing. Its remainder modulo 125 is $25 \times 4 = 100$, because the part left after removing the fives is 4 modulo 5. Kummer supplies the power of the prime; Granville supplies the digits of what the power multiplies. Together they fix the coefficient’s last digits in base $p$ to as many places as the carries plus the width of a window: first the trailing noughts Kummer counts, one per carry, then $q$ more digits read from the windows.

The same failure in base three #

In base three the small coefficients are no longer all 1 — $\binom{2}{1} = 2$ — so the digit product takes more values than in base two, and it is still wrong.

The hues repeat on blocks of three, nine and twenty-seven rows exactly as the triangle modulo three did, because hue is what one digit at a time decides. The depths are a different matter. A window of two digits straddles the boundary between one block and the next, so the second digit of a remainder in a lower block depends on the leading digit of $n$ together with the digit below it — and a block that copies the one above it in hue need not copy it in depth. It already fails in base two at the smallest scale: rows 2 and 3 copy rows 0 and 1 in hue, and $\binom{3}{1} = 3$ stands where $\binom{1}{1} = 1$ stood. In base three the one-digit rule is wrong at 93 of 216 units; that is 43 in a hundred, close to the 41 in a hundred it was wrong at in base two.

The count is not a sign of disorder. Every one of those 378 remainders is computed by a rule with no exceptions, and the figure checks each against the entry itself. What is lost modulo $p^2$ is not structure but the independence of the columns.

Rows that repeat much further than they need to #

Lucas’ theorem has one consequence that looks like it should be the end of the story: $\binom{pn}{pk}$ and $\binom{n}{k}$ leave the same remainder modulo $p$, because appending a nought to both $n$ and $k$ in base $p$ appends a column whose small coefficient is $\binom{0}{0} = 1$. Every $p$-th row of the triangle, read at every $p$-th place, is the triangle again, modulo $p$.

It is the triangle again to far more precision than that.

For every prime from five on, $\binom{pn}{pk}$ and $\binom{n}{k}$ agree modulo $p^3$. Charles Babbage proved the case $\binom{2p-1}{p-1} \equiv 1$ modulo $p^2$ in 1819, Joseph Wolstenholme raised it to $p^3$ in 1862, and the general form for every $n$ and $k$ came in the middle of the twentieth century, from Wilhelm Ljunggren and Ernst Jacobsthal.

The Babbage–Wolstenholme case has a proof that shows where the cube comes from. Write

$$\binom{2p-1}{p-1} = \prod_{i=1}^{p-1} \frac{p+i}{i} = \prod_{i=1}^{p-1}\left(1 + \frac{p}{i}\right) = 1 + p\sum \frac1i + p^2 \sum_{i<j}\frac{1}{ij} + \cdots,$$

working modulo $p^3$ with $1/i$ meaning the inverse of $i$ on that dial. The terms from $p^3$ on vanish, and two correction terms are left.

The first needs the sum of the inverses to be a multiple of $p^2$. Pair $i$ with $p - i$: $1/i + 1/(p-i) = p/\big(i(p-i)\big)$, so the sum is $p$ times half the sum of the fractions $1/\big(i(p-i)\big)$ — and modulo $p$ each of those is $-1/i^2$. The second needs the sum over pairs $\sum_{i<j} 1/(ij)$ to be a multiple of $p$, and that sum is half of the square of the first sum minus the sum of the squared inverses. Both come down to one fact: the squared inverses add up to a multiple of $p$. They run over the same values as the squares $1^2, 2^2, \dots, (p-1)^2$, whose sum $(p-1)p(2p-1)/6$ is a multiple of $p$ as soon as the six in the denominator shares no factor with $p$ — from five on, and not before.

For $p = 3$ the argument runs out a step early, and the second figure shows the exact place. $1 + 1/2$ is $3/2$, divisible by three once and not twice, so the $p$-term survives modulo 27 and the agreement stops at nine. The shaded cells are where it stops, and the first of them is the entry the proof names: $\binom{6}{3} = 20$ and $\binom{2}{1} = 2$ differ by eighteen.

Where the rule needs its hypotheses #

The modulus must be a prime power. A remainder modulo 12 is a remainder modulo 4 and a remainder modulo 3 read together, so a composite modulus is handled by running the rule once per prime power and assembling the answers. There is no single base in which the digits of a composite modulus live, which is why no single digit rule exists for it.

The prime is removed before the rule speaks. Granville’s theorem describes the coefficient divided by its full power of $p$, not the coefficient. When that power is $q$ or more the remainder modulo $p^q$ is simply nought and all the information is in what the power multiplies — as $\binom{100}{37}$ showed, where the useful statement was about the remainder modulo 125.

The sign depends on the dial. It is there for every odd prime power and for 4, and absent for 8, 16 and every higher power of two, for the reason a group of units without a generator has more than one element of order two.

The windows grow with the modulus and the work does not grow much. Modulo $p^q$ each window has $q$ digits and there is one window per digit of $n$, so the rule costs a few small factorials per digit — a computation on $\log n$ digits, against a coefficient with about $n$ of them, which is the same saving the carry count made for the power of $p$.

Two digits of shading, and a rule with no such limit #

The shaded triangles have two digits of remainder to show and a colour for each, which is why they stop at $p^2$: modulo 27 there would be three digits and no honest way to shade the third. The worked table has no such limit, and the rule it computes has none; the figures that draw every entry simply do not go further than a picture can carry.

The pictures also check finitely many cases. Thirty-two rows modulo four and twenty-seven modulo nine is 906 entries, each computed by the rule and compared with the entry; the comparison of every fifth row with the triangle runs to $n = 24$. That is evidence the rule was implemented correctly. The proof above is what makes it true.

And the split-pair description of the remainder modulo 4 is special to base two. It works because every binary window of an odd entry is either $11$ split, $11$ unsplit or something whose factorials are all 1; in base three the ratio for a window takes more values, and the rule has no description in words as short as that one.

Still open: one power beyond the cube #

The Babbage–Wolstenholme congruence says $\binom{2p-1}{p-1}$ leaves 1 modulo $p^3$ for every prime from five on. For most primes it does not leave 1 modulo $p^4$. The primes for which it does are called Wolstenholme primes, and only two are known — 16,843 and 2,124,679 — although a heuristic count suggests there are infinitely many of them, appearing more and more rarely.

The converse is open too. Every prime from five on satisfies the congruence modulo $p^3$; no composite number $n$ is known for which $\binom{2n-1}{n-1}$ leaves 1 modulo $n^3$, and nobody has proved that none exists. If none does, the congruence is a test for primality stated entirely in terms of one entry of Pascal’s triangle — the same shape of statement as Wilson’s characterisation, and like it, far too slow to use.

A rule that fails may have been read too finely #

The habit is about what to do when a clean rule stops working one step further out.

Lucas’ theorem fails modulo $p^2$, and the tempting conclusion is that the remainders modulo $p^2$ have no digit rule — that above the first power the triangle turns arithmetic into noise. The dots in the first figure look like evidence for it. The rule that replaces it is still a digit rule; it reads the digits two at a time instead of one. The one-digit rule was not wrong about the kind of answer, only about its width.

That is a common shape, and worth checking for before reaching for a different kind of explanation. When an argument that works column by column breaks, find the term that couples neighbouring columns — here the middle coefficients of $(1+x)^p$ — and ask how far the coupling reaches. If it reaches one column, read pairs; if it reaches $q - 1$ columns, read windows of $q$. The failure measured how wide the rule had to be.