Pascal's Triangle mod p — Binomial Coefficients as Fractals

Binomial coefficients, one row at a time

Pascal's triangle builds row n from row n−1 with one rule: each entry is the sum of the two entries diagonally above it, edges padded with 1. Row n, position k, holds the binomial coefficient C(n, k) — the number of ways to choose k items from n, and the coefficient of xᵏ in the expansion of (1 + x)ⁿ. It's named for Blaise Pascal's 1654 treatise, though the triangle itself was known centuries earlier in India, Persia and China (where it's called Yang Hui's triangle). Colouring each cell by its value modulo a small prime p turns this ordinary combinatorial table into a display of self-similar fractal structure.

live demo · Pascal's triangle mod p, coloured by residue class● LIVE

row[0] = [1]
row[n][k] = row[n-1][k-1] + row[n-1][k]     (with row[n][0] = row[n][n] = 1)

// reduced mod p, this is all that's needed:
cellModP = (row[n-1][k-1] + row[n-1][k]) % p

Mod 2: the Sierpinski triangle falls out for free

Colour every odd entry black and every even entry white, and Pascal's triangle mod 2 renders as the Sierpinski triangle — exactly, not approximately, and the resemblance sharpens as you compute more rows rather than being a coincidence of a few dozen rows. This isn't an accident of visualisation; it's a theorem. Lucas’ theorem (1878) says C(n, k) mod p (for prime p) can be computed digit-by-digit in base p: write n and k in base p as n = nₘ...n₁n₀ and k = kₘ...k₁k₀, then C(n, k) mod p = the product of C(nᵢ, kᵢ) mod p over every digit position, and the whole product is zero (mod p) the instant any single digit pair has kᵢ > nᵢ. For p = 2, that means C(n, k) is odd exactly when every binary digit of k is ≤ the corresponding binary digit of n — precisely the recursive "is a 1-bit a subset of a 1-bit" condition that generates the Sierpinski gasket's self-similar removal pattern.

Other primes: fractals with p-fold branching

Lucas' theorem generalises cleanly to any prime p, and the resulting mod-p pattern is again self-similar, but now built from p(p+1)/2 smaller similar copies of itself arranged in a triangular super-structure, rather than the 3 copies (mod 2's Sierpinski triangle) case. Mod 3 shows a pattern of triangular cells with sixfold internal structure; mod 5 and mod 7 grow progressively finer and busier. Each of these has a rigorously computable fractal dimension: for prime p it works out to log(p(p+1)/2) / log(p), which equals log 3 / log 2 ≈ 1.585 exactly when p = 2 (the familiar Sierpinski triangle dimension) and increases slowly toward 2 as p grows, because a larger prime allows more of the (n mod p, k mod p) digit combinations to be nonzero.

Why this connects Pascal's triangle to number theory at all

The deep reason a purely combinatorial object (counting subsets) reduces to a purely digit-based rule (Lucas' theorem) is Kummer’s theorem: the exponent of prime p dividing C(n, k) equals the number of carries when you add k and (n − k) in base p. When there are zero carries — which is exactly the "every digit of k fits inside the corresponding digit of n" condition — the binomial coefficient isn't divisible by p at all, so it survives mod p as a nonzero residue; wherever a carry occurs, the coefficient is divisible by p and vanishes mod p, punching the self-similar holes that make the fractal pattern.

From a triangle to a computational trick

Lucas' theorem isn't just decorative — it's a practical algorithm. Computing C(n, k) mod p directly for enormous n and k (millions or more) by building the full triangle is infeasible, but decomposing n and k into base-p digits and multiplying together at most log_p(n) small binomial coefficients (each looked up from a tiny precomputed table) computes the answer in time logarithmic in n. This is a standard technique in competitive programming and computational number theory whenever a binomial coefficient modulo a small prime is needed for very large n.

Frequently asked questions

Why does Pascal's triangle mod 2 look exactly like the Sierpinski triangle?

By Lucas' theorem, C(n,k) is odd if and only if every binary digit of k is less than or equal to the corresponding binary digit of n. That bitwise subset condition is precisely the recursive rule that generates the Sierpinski triangle's self-similar pattern of filled and empty cells, so the two constructions coincide exactly, not approximately.

Does the fractal pattern appear for every prime, or just 2?

Every prime p produces a self-similar fractal pattern when you color Pascal's triangle by residue mod p, via the same Lucas' theorem digit-by-digit rule generalized to base p. The fractal dimension increases slowly with p, from log(3)/log(2) at p=2 toward 2 as p grows, because larger primes permit more nonzero digit combinations.

What is Kummer's theorem and how does it relate to Lucas' theorem?

Kummer's theorem says the exponent of prime p dividing C(n,k) equals the number of carries that occur when adding k and n-k in base p. Zero carries means the coefficient isn't divisible by p at all (Lucas' subset condition is satisfied); any carry means it vanishes mod p — the carries are exactly what punch the self-similar holes in the fractal.

Try it live

Everything above runs in your browser — open Pascal's Triangle mod p and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Pascal's Triangle mod p simulation

Pascal's Triangle mod p: The Fractal Hiding in Binomial Coefficients