ABC Tools

Pascal's Triangle mod n, Explained

After reading this you will be able to predict which entries of Pascal's triangle vanish under a given modulus, read the fractal that results, and connect the picture to Kummer's and Lucas's theorems.

What the picture is

Pascal's triangle stacks the binomial coefficients \binom{n}{k} row by row. Row 0 is a single 1. Every later entry is the sum of the two entries just above it. Rows 0 through 4 read 1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1.

The numbers grow fast. Row 20 already contains \binom{20}{10} = 184756. The colours you see do not track those raw sizes. They track the remainder when each entry is divided by a chosen modulus n. Pick n = 2 and every entry becomes either 0 (even) or 1 (odd). Colour the odd ones and leave the even ones blank, and the Sierpinski triangle appears: a triangle of triangles of triangles, holes inside holes, at every scale you care to draw.

That is the hook. A rule about adding two integers, applied a few hundred times, draws a fractal with a fractional dimension. The rest of this article explains why.

When to reach for this, and when not

Use the colour-by-remainder view when you want to see divisibility structure in the binomial coefficients. It answers questions like: how often is \binom{n}{k} divisible by 3? Which rows are entirely odd? Why do the holes sit where they sit? These are number-theory questions with clean visual answers.

Do not use it to reason about the sizes of the coefficients. The remainder throws away almost all the magnitude. An entry of 6 and an entry of 1000006 both show as 0 mod 2. If you care about how large the numbers get, or about the bell shape of a single row, that shape is invisible here. And a toy render of 256 rows is not a proof of anything. It suggests patterns; Kummer and Lucas prove them.

The self-similarity is exact, not approximate. It is not an artifact of pixel rounding. The mod-2 triangle repeats its own top half in each of two lower corners forever, and you could zoom in on the true infinite triangle without ever hitting a smallest feature.

The rule and the two theorems behind it

The build rule is Pascal's identity, and it holds under any modulus because addition commutes with taking remainders.

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}

Here \binom{n}{k} is the entry in row n, position k, counting both from 0. To colour it mod m you only need the previous row's remainders, added and reduced. You never touch the huge exact values.

Why do holes appear? Kummer's theorem answers it for a prime p.

v_p\!\left(\binom{n}{k}\right) = \text{number of carries when adding } k \text{ and } n-k \text{ in base } p

The symbol v_p counts how many times p divides the coefficient. So \binom{n}{k} is divisible by p exactly when adding k and n-k in base p forces at least one carry. No carry, no factor of p, and the entry is nonzero mod p.

Lucas's theorem restates the same fact digit by digit. Write n and k in base p as n = n_r p^r + \cdots + n_0 and k = k_r p^r + \cdots + k_0. Then

\binom{n}{k} \equiv \prod_{i=0}^{r} \binom{n_i}{k_i} \pmod{p}

Each factor uses one base-p digit of n and the matching digit of k. If any digit of k is larger than the digit of n in the same place, that factor is \binom{n_i}{k_i} = 0, so the whole product is 0 mod p. Those zeros are the holes.

Worked example: reproduce the mod-2 default

The demo starts with the field defaults: modulus 2. Let us verify Lucas by hand on a single row and confirm the Sierpinski shape.

Which entries of row 6 are odd?

Row 6 is 1 6 15 20 15 6 1. In binary 6 = 110.

  1. Write each position k from 0 to 6 in binary: 000, 001, 010, 011, 100, 101, 110.
  2. Lucas mod 2 says \binom{6}{k} is odd only when every binary digit of k is \le the matching digit of 6 = 110. The middle and top bits may be 1; the bottom bit must be 0.
  3. That allows k \in \{000, 010, 100, 110\} = \{0, 2, 4, 6\}. Those four are odd.
  4. Check against the row: positions 0,2,4,6 hold 1, 15, 15, 1, all odd. Positions 1,3,5 hold 6, 20, 6, all even. Confirmed.

Notice a shortcut: \binom{n}{k} is odd exactly when k is a "submask" of n in binary, meaning k AND n == k. Row 6 (110) has exactly 2^2 = 4 submasks because it has two 1-bits.

That last count generalises. A row n with s one-bits in binary has exactly 2^s odd entries. Row 7 is 111, three one-bits, so 2^3 = 8 odd entries: the whole row is odd. Every row of the form 2^j - 1 is solid. Those solid rows are the bottom edges of the big Sierpinski triangles.

The count is always a power of 2, equal to 2 raised to the number of 1-bits in n. Rows 7 and 15 peak because 7 and 15 are all-ones in binary.

Reading other moduli

For a prime modulus p, the picture is the cleanest kind of fractal. Lucas turns each entry into a product of small building blocks drawn from the base-p triangle, which is just Pascal's triangle read mod p for rows 0 through p-1. That small triangle tiles the big one recursively. Mod 3 you get triangles built from a 3-row unit; mod 5 from a 5-row unit.

Composite moduli mix fractals. By the Chinese remainder theorem, a value mod 6 is fixed by its value mod 2 and mod 3 together. So the mod-6 image is the two prime patterns overlaid: an entry is 0 mod 6 only where it is 0 mod 2 and 0 mod 3 at once. The holes of mod 6 are the intersection of the mod-2 holes and the mod-3 holes, which is why composite pictures look busier and less obviously self-similar.

To judge whether a modulus is prime just by looking, count the distinct colours along the top few rows and check for one clean nested triangle. Primes give one motif repeating. Composites show two or more motifs interfering.

Without JavaScript: pick a prime p and a row n. Write n in base p. The number of nonzero entries in that row equals the product of (each base-p digit plus 1). For p = 3 and n = 7 = "21" in base 3, that is (2+1)(1+1) = 6 nonzero entries out of 8.

Common mistakes

The first mistake is treating a composite modulus as if Lucas applied directly. Lucas's product formula is a statement about primes. Mod 6 it fails: \binom{4}{2} = 6 \equiv 0, but if you naively applied a Lucas-style product with base 6 you would get the wrong answer. Split into primes instead.

The second mistake is confusing "even" with "small". The colour is parity or remainder, not size. Row 100 has enormous entries; mod 2 it still splits cleanly into odd and even by the binary submask rule alone.

The third is expecting the exact Sierpinski triangle for every modulus. Only mod 2 gives the classical three-way Sierpinski gasket whose fractal dimension is \log 3 / \log 2 \approx 1.585. Other primes give related but different fractals with their own dimensions. If you want to measure one of those dimensions directly, the Box-Counting Dimension Lab lets you lay grids over the pattern and read the slope.

Related tools

The same Sierpinski triangle shows up from three unrelated recipes on this site, which is the real lesson. The Chaos Game grows it from random corner-hopping. Elementary Cellular Automata rule 90 is Pascal mod 2 in disguise: rule 90 XORs its two neighbours, which is exactly addition mod 2. And the Abelian Sandpile produces its own nested triangular symmetry from toppling grains.

For more number theory rendered as pictures, try the Modular Times Table, the Ulam Prime Spiral, and the Sieve of Eratosthenes. For other classic fractals, the Mandelbrot Explorer and Newton Fractal come from iteration in the complex plane rather than from arithmetic.

Frequently asked questions

Why does mod 2 give exactly the Sierpinski triangle?

Because the odd entries are the binary submasks of the row number, and that submask rule tiles the same triangular gap at every power-of-two scale. Each solid row 2^j - 1 caps a triangle, and the even entry directly below two odd corners opens the central hole. The result is three copies of the top half arranged around an empty middle, forever.

How many entries in row n are not divisible by a prime p?

Write n in base p with digits n_0, n_1, \ldots, n_r. The count of nonzero entries mod p is \prod_i (n_i + 1). For n = 7 and p = 3, that is 7 = 21 in base 3, giving (2+1)(1+1) = 6 of the 8 entries nonzero.

What is the fractal dimension of the mod-2 pattern?

It is \log 3 / \log 2 \approx 1.585. Each time you double the scale, the number of filled triangles triples, so the dimension is the log of 3 over the log of 2. It lies between 1 (a line) and 2 (a filled area), as a fractal should.

Do composite moduli ever look self-similar?

They repeat at a scale set by their prime power factors, but they superimpose several patterns, so the eye rarely reads a single clean motif. Mod 6 is the mod-2 and mod-3 fractals laid on top of each other, and its holes are only where both agree.

Is rule 90 really the same thing?

Yes. Rule 90 replaces each cell with the XOR of its two neighbours, and XOR is addition mod 2. Seed a single cell and the time-evolution reproduces Pascal's triangle mod 2 row by row, the same Sierpinski gasket.

Try it yourself in the tool

Related tools

3D Geometry Board

Points, lines, planes, spheres and polyhedra on an orbiting camera — slice solids with planes, unfold nets, drop the Dandelin spheres into a cone and drag everything.

Bézier Curve Playground

Drag control points and watch De Casteljau’s algorithm construct a Bézier curve step by step.

Central Limit Theorem Demo

Sample from any lopsided distribution and watch the averages pile up into a bell curve.

Conway’s Game of Life

Paint cells and watch Conway’s cellular automaton breed gliders, guns and oscillators.

Dynamic Geometry Board

Construct with points, lines, circles and transformations, then drag anything — the construction stays true, and a checker tells you which relations are theorems.

Fantasy Map Generator

Roll a seed and get a continent: coastlines, mountains, rivers, biomes and named towns, ready for your campaign.