Arrangements and Combinations · Lucas Theorem and the Sierpiński Triangle (Optional)

Lesson 14

Nikolai Chukhin · Alexander S. Kulikov

The same idea works modulo any prime \(p\). For \(p=3\), every entry has residue \(0\), \(1\), or \(2\); for example, one may color \[0=\text{white},\qquad 1=\text{blue},\qquad 2=\text{red}.\] For \(p=5\), there are five colors. The exact color of every cell is still determined by Lucas's theorem digit by digit.

Here are complete power pictures for several moduli: \(3^{4}\) rows modulo \(3\), \(5^{3}\) rows modulo \(5\), \(6^{3}\) rows modulo \(6\), and \(7^{3}\) rows modulo \(7\). Entries divisible by the modulus are shown in light gray, and the other entries are colored according to their residue.

The modulus \(6\) is included only as a comparison: it is not prime, so Lucas's theorem does not apply to it directly. However, its pattern is still structured because residues modulo \(6\) are determined by residues modulo \(2\) and modulo \(3\).

This happens because of the following. Suppose \[n=ap^{r}+n',\qquad k=bp^{r}+k',\] where \(0\le a,b<p\) and \(0\le n',k'<p^{r}\). Then Lucas's theorem gives \[\binom{n}{k}\equiv \binom{a}{b}\binom{n'}{k'}\pmod p.\] Thus each large block is either zero (when \(b>a\)) or a scaled copy of the smaller pattern. For \(p=2\), the only nonzero scale is \(1\), so the pattern is the usual Sierpiński triangle. For larger primes, Pascal's triangle modulo \(p\) produces a \(p\)-ary analogue of the same fractal behavior.