🔺 Pascal's Triangle mod p
Compute binomial coefficients C(n,k) modulo a small prime and colour each cell by its residue. Mod 2 reveals the Sierpinski triangle exactly, by Lucas' theorem — other primes reveal their own self-similar fractal patterns.
Compute binomial coefficients C(n,k) modulo a small prime and colour each cell by its residue. Mod 2 reveals the Sierpinski triangle exactly, by Lucas' theorem — other primes reveal their own self-similar fractal patterns.
This tool builds Pascal's triangle row by row using the recurrence C(n,k) = C(n-1,k-1) + C(n-1,k), but instead of letting the numbers grow without bound, every addition is reduced modulo a small prime p. The result is no longer a triangle of huge integers — it is a triangle of just p possible residues, and when those residues are coloured, a strikingly regular fractal appears. For p = 2, the pattern is exactly the Sierpinski triangle, a consequence of Lucas' theorem on binomial coefficients modulo a prime.
Each cell (n,k) of the triangle holds C(n,k) mod p, computed with an in-place rolling-array version of Pascal's recurrence so even 256 rows compute instantly. In fractal mode, residue 0 is left blank and the other p−1 residues get distinct colours, revealing self-similar triangular patterns that repeat at every scale.
Drag the rows slider to compute more or fewer rows, pick a modulus of 2, 3, 5 or 7, and switch between the colour-coded fractal view and the exact-integer view (limited to 14 rows so the numbers stay readable). Try each of the three colour schemes to see the residue structure differently.
Kummer's theorem says the exact power of p dividing C(n,k) equals the number of carries when adding k and n−k in base p — so the fractal you see is literally a picture of carrying (or not carrying) during addition.
By Lucas' theorem, C(n,k) mod 2 equals 1 precisely when every binary digit of k is less than or equal to the corresponding binary digit of n (equivalently, k AND n = k). Colouring cells where this holds and leaving the rest blank produces, row by row, exactly the same recursive triangular hole pattern as the classical Sierpinski triangle construction — not an approximation, but an exact bit-level match.
Lucas' theorem states that for a prime p, C(n,k) mod p can be computed by writing n and k in base p digit by digit and multiplying the binomial coefficients of the matching digits mod p: C(n,k) ≡ ∏ C(ni,ki) (mod p). If any digit of k exceeds the matching digit of n, one of those factors is zero, so the whole product is zero — which is exactly why blank (zero) cells appear where they do.
Lucas' theorem applies for any prime, but the digit-comparison rule works in base p, not base 2. For p = 3 the triangle is divided into a self-similar arrangement of 3×3-scaled copies rather than 2×2, and more residue classes (0, 1, 2, ...) are possible, so the pattern has richer internal colouring and different symmetry than the strictly binary Sierpinski case.
The true value of C(256,128) has around 75 digits, far beyond what standard 32- or 64-bit integers can hold, and would require slow arbitrary-precision arithmetic to compute exactly. Because only the remainder mod p is needed, every intermediate sum can be reduced back down to a number between 0 and p−1 at each step, keeping all arithmetic in small fast integers no matter how many rows are computed.
Beyond being a visually striking fractal, binomial coefficients mod p are central to combinatorics on finite fields, coding theory, and cellular automata (Pascal's triangle mod 2 is closely related to Rule 90 in Wolfram's elementary cellular automaton classification). The same digit-wise structure from Lucas' theorem also appears in fast algorithms for computing binomial coefficients modulo a prime in competitive programming and cryptography.