The carries decide the divisibility

The rung below shaded the odd entries of Pascal’s triangle and found the Sierpiński triangle, and explained it with Lucas’ theorem: an entry is odd exactly when the binary digits of $k$ sit under those of $n$. That settles which entries are divisible by two and says nothing about how often.

Kummer’s answer, from 1852, is startling on first reading and has nothing to do with choosing.

The exponent of $p$ in $\binom{n}{k}$ is the number of carries when $k$ and $n-k$ are added in base $p$. That is a statement about the mechanics of column addition, and it is exactly equal to a statement about divisibility — a question about what a number’s divisors look like answered by looking at how two other numbers are written.

Why a carry is a divisibility #

The proof is a comparison of two counts and it is short enough to give.

Legendre’s formula says the exponent of $p$ in $m!$ is

$$\left\lfloor \frac{m}{p}\right\rfloor + \left\lfloor \frac{m}{p^2}\right\rfloor + \left\lfloor \frac{m}{p^3}\right\rfloor + \cdots,$$

because the first term counts the multiples of $p$ up to $m$, the second counts those divisible by $p^2$ a second time, and so on. So the exponent in $\binom{n}{k} = n!/(k!\,(n-k)!)$ is the alternating combination of three such sums.

Now the digits. Write $s_p(m)$ for the sum of the base-$p$ digits of $m$. Legendre’s formula collapses to

$$\text{exponent of } p \text{ in } m! = \frac{m - s_p(m)}{p-1},$$

which is a rearrangement rather than a new idea: each digit of $m$ contributes to the floors below it in a pattern that adds up exactly that way.

Substituting,

$$\text{exponent in } \binom{n}{k} = \frac{s_p(k) + s_p(n-k) - s_p(n)}{p-1}.$$

And there is the carry. Adding $k$ and $n-k$ digit by digit, each carry replaces a digit sum of $p$ or more by a digit $p$ less and adds one to the column above — so each carry reduces the total digit sum by exactly $p-1$. The numerator counts the total loss and the division by $p-1$ turns it into a count of carries.

That is the whole argument, and the pleasing part is which step is doing the work. Legendre’s formula is about multiples; the digit-sum form is about place value; and the bridge between them is that dividing by $p$ and taking a floor is the same as dropping a digit.

The two extremes #

No carries at all means the exponent is nought, which means the entry is not divisible by $p$. Adding $k$ and $n-k$ without a carry means every column sums to less than $p$, which for $p = 2$ means $k$ and $n-k$ never have a one in the same place — which means the binary digits of $k$ sit under those of $n$. That is Lucas’ theorem, recovered as the case of no carries.

So the rung below’s fractal is the exponent-zero level set of the picture on this page. The Sierpiński triangle is where no carry happens, and everything shaded there is where at least one does.

Every column carrying is the other extreme and gives the largest exponent available. The largest is bounded: a carry can only happen in a column, and $n$ has about $\log_p n$ of them, so the exponent of $p$ in any entry of row $n$ is at most $\log_p n$. A binomial coefficient of a hundred digits is divisible by two at most seven times, which is a much stronger statement than the size of the number suggests and follows from nothing but the column count.

The whole triangle at once #

Computing the exponent at every entry of a triangle gives a picture, and the picture is a refinement of the rung below’s.

The blank region is the parity fractal, and the shaded regions are organised the same way, because the count of carries is a digit-by-digit statement and digits are a self-similar structure. The whole picture is a stack of Sierpiński triangles, one for each exponent, and the rung below’s figure is the top layer.

That the two pictures differ only in their block size is the content of Kummer’s theorem restated visually. Nothing about the arithmetic changes with $p$; what changes is how many digits a number has and how easily a column overflows.

The self-similarity has an exact statement worth having, because it is the reason the pictures repeat rather than merely resembling themselves. Adding a new leading digit to $n$ adds a column that the addition of $k$ and $n-k$ may or may not carry out of, and whether it does depends only on that column and on the carry arriving from below. So the picture for rows $0$ to $p^{m+1}$ is built from $p$ blocks each of which is the picture for rows $0$ to $p^m$, with the exponent raised by one in the blocks where the new column carries.

That is a construction rule for the whole family, and it says the shading is not approximately self-similar but exactly so, at every scale, with the deeper shades appearing precisely where a higher column carries. A fractal that is drawn by a rule about place value has no approximation in it at all, which distinguishes these pictures from the attractors of a dynamical system that look the same and are not.

Why the exponent is small, and why that matters #

The bound of $\log_p n$ deserves a second look, because it says something about binomial coefficients that is not obvious from any other description.

$\binom{100}{50}$ is about $10^{29}$. Its prime factorisation contains only primes up to $100$ — there are twenty-five of them — and each appears at most $\log_p 100$ times, which is seven for $p = 2$ and one for every prime above $10$. So a number of twenty-nine digits is a product of twenty-five small primes with small exponents.

A binomial coefficient is enormous and its factorisation is short, and that is the reason so many arguments about primes go through them.

The sharpest consequence is a fact about the primes between $n$ and $2n$. Take $p$ in that range and ask how often it divides $\binom{2n}{n}$: adding $n$ and $n$ in base $p$, the number $n$ is a single digit — since $p > n$ — and the column sums to $2n$, which is at least $p$, so there is exactly one carry. Every prime strictly between $n$ and $2n$ divides the central coefficient exactly once, and none divides it twice.

That single sentence is most of a proof that such a prime exists. The coefficient is at least $4^n/(2n+1)$, which is large; every prime factor is at most $2n$; the ones below $\sqrt{2n}$ can contribute at most $2n$ each by the logarithm bound; and the ones between $2n/3$ and $n$ contribute nothing at all, by a second carry count. If no prime lay between $n$ and $2n$ the remaining factors could not account for the size, and there is always one.

Every step of that is a carry count. The theorem on this page is not an ingredient of the argument; it is the argument, with the size bound supplying the contradiction. Erdős’ proof of Bertrand’s postulate — that there is always a prime between $n$ and $2n$ — works by bounding $\binom{2n}{n}$ from below by its size and from above by its factorisation, and the upper bound is exactly Kummer’s theorem doing the work.

The same shape of argument runs through most elementary results about the distribution of primes. The coefficient is big; its prime factors are constrained; therefore there must be enough of them; therefore primes exist where they were claimed to. The size and the factorisation are two independent handles on one number, and Kummer’s theorem is what makes the second one exact.

What it costs to answer #

The two computations the figures run cost very different amounts, and the difference is the practical value of the theorem.

By Legendre’s formula, the exponent of $p$ in $\binom{n}{k}$ is a sum of about $\log_p n$ floors for each of three factorials — thirty operations for $n$ in the hundreds, and it never forms the coefficient.

By counting carries, it is one pass of column addition over $\log_p n$ columns, which is the same order and slightly cheaper.

By computing the coefficient and dividing, it is a multiplication and a division for each of $k$ steps to build a number with $n$ digits in it, and then repeated division. For $\binom{1000}{500}$ that is a number with two hundred and ninety-nine digits, and every operation on it costs proportionally.

So the theorem turns a question about an enormous number into a question about its inputs’ digits, and the saving is not marginal — it is the difference between arithmetic on $n$ digits and arithmetic on $\log n$ of them. The exponent was never a property that needed the number, which is a common shape: a quantity defined in terms of an object often depends on far less of the object than its definition suggests.

That is also the reason the two computations are worth running against each other in a figure rather than trusting one. They share no step: one is a sum of floors, the other is a carry count, and the only thing connecting them is the theorem. Two implementations of a theorem agreeing is evidence the theorem was implemented; one implementation agreeing with itself is evidence of nothing.

What happens between the primes #

The picture for a single prime is a stack of self-similar layers, and a natural question is what the entry looks like when every prime is taken into account at once.

The answer is that the pictures are independent. The exponent of two and the exponent of three are computed from different digit expansions of the same pair of numbers, and there is no relation between them — a row can have entries divisible by two many times and by three not at all, and the two shaded triangles for the same rows look nothing alike beyond both being self-similar.

That independence has a consequence for the composite case. The behaviour of a coefficient modulo six is determined by its behaviour modulo two and modulo three together, so the modulo-six picture is the superposition of two self-similar patterns with different block sizes — and a superposition of a two-scale pattern and a three-scale one is self-similar at scale six, but with a period that takes six times as many rows to become visible.

So the composite pictures are not messier because something breaks; they are messier because two independent structures are being seen at once. Lucas’ theorem fails for a composite modulus for the same reason: it is a statement about one base, and a composite modulus corresponds to no single base.

The general principle is worth keeping. A question about divisibility by a composite number is a question about each of its prime powers separately, and the pictures obey that decomposition exactly. What is lost in going to a composite is not structure but the ability to see the structure in one picture.

Where it needs its hypotheses #

The base must be prime. Legendre’s formula counts multiples of $p$, $p^2$ and so on, and the count is right only because a prime power’s contribution is a simple floor. For a composite modulus the digit argument survives and the divisibility statement does not, which is why the rung below’s modulo-three and modulo-five pictures are self-similar and a modulo-six one is messier.

The exponent is about $p$ and not about a prime power. A prime is the atom of divisibility and this theorem is about one atom at a time. Kummer’s theorem gives the exact power of $p$ dividing the entry; the entry’s behaviour modulo $p^2$ is a further question with a further answer (Granville’s extension of Lucas’ theorem), and it is considerably less tidy.

The carries depend on the pair, not on $n$ alone. Two entries of the same row can have completely different exponents, and the picture makes that visible — a row of the shaded triangle is generally not uniform in colour.

And the coefficient has to be computed exactly. This is the one hypothesis about the figure rather than the mathematics, and it caught a version of it: $\binom{100}{37}$ has twenty-nine digits, a double-precision number carries sixteen, and dividing a rounded value by two six times to check that six is the right exponent gives a residue that means nothing. The figures compute the coefficient in exact whole numbers for that reason.

Kummer, and what he was doing #

Ernst Kummer proved this in 1852, and he was not investigating Pascal’s triangle. He was working on Fermat’s last theorem, and specifically on the failure of unique factorisation in the rings of cyclotomic integers — the failure he repaired by inventing ideal numbers, which is the origin of the modern notion of an ideal.

Binomial coefficients turn up in that work because the exponents of primes dividing them control the divisibility of certain sums, and the carry criterion was the tool he needed rather than the result he was after. It is now the more famous of the two, which is the usual fate of a clean lemma inside a difficult programme — the Lagrange remainder is the same story in analysis.

Lucas proved his own theorem in 1878, twenty-six years later, and it is the special case. The order is worth knowing because it is the opposite of the order they are usually taught: the general statement came first, was forgotten outside a specialist literature, and the special case was rediscovered and became the famous one.

What the pictures cannot show #

The column-addition figure shows one pair of numbers in one base, and the theorem is about every $n$, every $k$ and every prime. The shaded triangles check every entry of twenty-seven rows — three hundred and seventy-eight of them, both ways — which is a lot of instances and no proof.

The shaded pictures also cannot show the exponent past the fifth, since there are only so many distinguishable shades, and the deepest cells in a large triangle would need more. The figures use a small enough triangle that the range fits.

And nothing here draws the connection the essay is mostly about. That the blank cells of the shaded triangle are the rung below’s fractal is a statement about two pictures, and the two are drawn on the same page and never superimposed — because a superposition would be a picture with one region shaded two ways, which says less than either.

The ladder from here #

Rungs above: Granville’s extension, which computes the coefficient modulo $p^2$ and $p^3$ and needs a correction term the digit argument does not supply. The composite moduli, where the pattern is messier and more interesting and Lucas’ theorem simply fails. The Chinese remainder assembly of those pictures, which recovers the composite case from the prime ones. Erdős’ proof of Bertrand’s postulate in full, where this theorem is the load-bearing bound. And the exponent’s average behaviour over a row, which is a question about digit sums and has an answer with a logarithm in it.

A question about numbers, answered by their notation #

The habit is the one worth arguing with, because it looks like a violation of a rule this collection otherwise keeps.

Divisibility is a property of a number and not of how it is written. A number divisible by three stays divisible by three in every base, and any criterion phrased in terms of digits is phrased in terms of a representation that the property does not depend on.

And yet the answer here is a fact about column addition in a particular base. The resolution is that the base is the prime, and base-$p$ notation is not an arbitrary choice for a question about $p$ — it is the notation in which the multiples of $p$, of $p^2$ and so on are visible as trailing zeros. Writing a number in base $p$ is exactly the act of separating out the powers of $p$ it contains.

So the rule survives, sharpened: a criterion in terms of digits is suspicious unless the base is chosen by the question. The divisibility-by-nine test in base ten is the same phenomenon and it is usually presented as a trick, when it is the statement that ten is one more than nine and so every power of ten is one more than a multiple of nine. Choose the base to suit the divisor and the digits stop being notation and start being the decomposition the question was about.