Pascal Modulo m

Place a 1 at the top of a triangle. Each new row begins and ends with 1; every inside entry is the sum of the two entries immediately above it. This gives the rows 1; 1, 1; 1, 2, 1; and 1, 3, 3, 1, the beginning of Pascal's triangle.

Divide each entry by 2 and keep its remainder. An even entry leaves 0 and an odd entry leaves 1, so 1, 2, 1 becomes 1, 0, 1. Colour the 1s and leave the 0s blank.

As the triangle grows, repeated triangular gaps appear. Each displayed triangle is a finite stage of the pattern associated with the Sierpiński gasket, not the entire infinite fractal. Changing the divisor from 2 changes the remainders and the colours being compared.

Watch what parity does to the addition rule. Odd + odd is even; odd + even is odd; even + even is even. So the parity of an entry depends only on the parities above it, and the triangle of 0s and 1s builds itself without ever consulting the actual coefficients.

That already explains why the pattern is possible - parity is self-contained, so nothing about the enormous numbers further down can interfere with it.

It does not explain why the pattern is a fractal. For that, notice which rows are entirely odd: 1, 3, 7, 15, 31. Each is one less than a power of two. A full row of 1s means the row beneath it is all 0s except at its ends - every interior entry is odd + odd - so a solid base is always followed by an empty row. And the structure that was built above that base then repeats, at twice the size, below it.

Solid rows at 2ᵏ − 1, doubling each time, is the gasket's construction, arrived at from the other direction.

Here is the whole thing in one sentence.

$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ is odd exactly when the binary digits of $k$ are a subset of the binary digits of $n$ - when $k$ has a 1 nowhere that $n$ has a 0.

Try it. Row 4 is $100$ in binary. The only positions whose bits fit inside $100$ are $000$ and $100$ - that is $k=0$ and $k=4$ - so row 4 has exactly two odd entries, and indeed 1, 4, 6, 4, 1 is odd, even, even, even, odd.

Row 7 is $111$. Every three-bit number fits inside $111$, so every entry of row 7 is odd. All eight of them.

This is why the count of odd entries in row $n$ is $2^r$, where $r$ is the number of 1s in $n$: a set of $r$ elements has exactly $2^r$ subsets. And it is why the pattern is self-similar - "fits inside" is a condition on digit strings, so it repeats every time the string gets one place longer, which is every power of 2.

Lucas' theorem. Let $p$ be prime, and write

with $0\le n_i,k_i<p$. Then

Two consequences, which are what this page draws:

1. $p\mid \left(\genfrac{}{}{0ex}{}{n}{k}\right)$ if and only if $k_i>n_i$ for at least one $i$. (One such place makes a factor $\left(\genfrac{}{}{0ex}{}{n_i}{k_i}\right)=0$.)
2. Taking $p=2$: the number of odd entries in row $n$ is $2^{s_2(n)}$, where $s_2(n)$ counts the 1s in the binary expansion of $n$.

Note carefully what is not claimed. Lucas requires $p$ prime. There is no equally simple statement for composite moduli, and this page does not pretend otherwise.

Work in ${\mathbb{F}}_p[x]$. The binomial theorem gives

and for $0<j<p$ the coefficient $\left(\genfrac{}{}{0ex}{}{p}{j}\right)=\frac{p!}{j!(p-j)!}$ has a factor of $p$ in its numerator and none in its denominator, since $p$ is prime and $j,p-j<p$. So every middle term vanishes modulo $p$:

Raising repeatedly, $(1+x{)}^{p^i}\equiv 1+x^{p^i}$. Now expand $n$ in base $p$ and split the polynomial along its digits:

Expand each factor. The $i$-th contributes $\left(\genfrac{}{}{0ex}{}{n_i}{k_i}\right)x^{k_i{p}^i}$ for some $0\le k_i\le n_i$. Because base-$p$ representations are unique, each exponent $k$ arises from exactly one choice of digits $k_i$ - so collecting the coefficient of $x^k$ on both sides gives

The two consequences follow directly. For the first: $\left(\genfrac{}{}{0ex}{}{n_i}{k_i}\right)=0$ when $k_i>n_i$, and otherwise it is a binomial coefficient of numbers smaller than $p$, hence not divisible by the prime $p$; a product of non-multiples of a prime is a non-multiple. For the second: at $p=2$ each digit factor is $\left(\genfrac{}{}{0ex}{}{1}{1}\right)=\left(\genfrac{}{}{0ex}{}{1}{0}\right)=\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$ or $\left(\genfrac{}{}{0ex}{}{0}{1}\right)=0$, so the entry is odd exactly when $k$'s bits sit inside $n$'s, and the number of such $k$ is $2^{s_2(n)}$.

This is what a proof buys you. No amount of drawing rows establishes the claim for row 1,000,000; three lines of polynomial algebra establish it for every row at once. Every other exploration in this guide is missing exactly this, and it is worth feeling the difference.

The fractal is a limit, and the screen is not. What this laboratory draws is a finite triangle - at most 512 rows. The Sierpiński gasket is what the parity pattern approaches when the drawing is scaled to a fixed size and the number of rows grows without bound. Every finite picture here is an approximation to it, and the resemblance at 256 rows is not evidence for the limit; the proof in layer 5 is.

Composite moduli are genuinely harder, not merely untidy. Try modulus 6 and the nesting degrades visibly. That is not a rendering artefact: Lucas needs a prime, and there is no comparably simple digit criterion for a composite. The general theory - Kummer's carry-counting result, and the extensions to prime powers - is real mathematics and substantially more involved than anything above. The claim on this page about composites is deliberately marked observed rather than proved, and its scope names the 512 rows it was measured over: at that size modulo 2 leaves 85.0% of the entries as holes and modulo 6 leaves 70.3%, and neither number is a theorem.

What this page is for. It is the control case in this collection. Gilbreath's left edge looks every bit as convincing as the gasket does and remains an open problem; the happy numbers are settled, but by exhausting a finite space rather than by an argument. Here the picture and the proof are the same object, and holding all three in mind is the most useful thing this guide can give you - because from the outside, a pattern with a proof behind it and a pattern without one look exactly alike.