Pascal Triangle and Prime Numbers

I’m not convinced this is MO-appropriate, but I’m posting an answer ’cause what I’d have to say is probably too long for a comment.

Expanding on Reid’s comment. Yeah, Lucas’ theorem is nice. Lucas’ theorem is one of a fair number of combinatorial results which can be thought of as “first steps towards p-adic numbers.” What’s that mean? There’s a “different” absolute value that you can define on rational numbers, which has a lot of the same properties as the usual absolute value, but in other ways behaves totally differently. Actually there are an infinite number of these guys, one for every prime $p$! It’s called the p-adic absolute value, and you can read about it on Wikipedia.

What the p-adic numbers do is help you to get around the following obstacle: Say you want to tell whether a quotient of two numbers, $\frac{a}{b}$, is divisible by $p$. (We’ll assume for now that $\frac{a}{b}$ is definitely an integer, although this ends up not mattering at all. But “divisibility” is a trickier notion for non-integers.) If $a$ is divisible by $p$ and $b$ isn’t, then it’s obvious that $\frac{a}{b}$ is; if $a$ isn’t divisible by $p$, then of course $\frac{a}{b}$ isn’t. But things get tough if both $a$ and $b$ are divisible by $p$; it could happen that $a$ is divisible by $p^2$, and $b$ is divisible by $p$ but not by $p^2$. Or that $a$ is divisible by $p^{17}$, and $b$ is divisible by $p^{14}$ but not by $p^{15}$. You see how this gets confusing! The p-adic absolute value encodes this sort of information for you.

This also explains why we don’t work with, say, 10-adic numbers in mathematics; it’s because if you take the integers but consider two integers to be the same if they have the same remainder when you divide by $n$, you can still multiply and add and subtract perfectly well. So you get something called a ring. And if $n$ is prime, you can also divide numbers! (Well, you can’t divide by 0, or by a multiple of the prime, which is “the same as” 0. But this is true no matter what, so it’s not a real problem.) But this isn’t true for composites.

Anyway, the patterns for primes in Pascal’s triangle are pretty well known. Google “Pascal’s triangle modulo” (without quotes, probably) to find more stuff. Composites don’t behave as nicely, for the reasons Wikipedia and I both briefly mentioned, but powers of primes do have interesting patterns, which you can read about in the wonderfully-titled paper “Zaphod Beeblebrox’s Brain and the Fifty-ninth Row of Pascal’s Triangle”.

Hope this helps!

I also wanted to give a very short answer. Let $p$ be a prime number. It is easy to see that the binomial coefficient $\left(p\atop n\right)$ is divisible by $p$ for $1\le n\le p-1$. So the $p$-th line looks like $1,0,0,\ldots,0,1$ mod $p$. Then by the recursive definition of the Pascal triangle a new triangle starts at the left and at the right (until they meet in the mid somewhere). And this process goes on and on. Probably the line $\left(p^2\atop *\right)$ is also a line with this property, etc. This explains the recursive nature of this phenomenon.

The mod 2 case is related to the Sierpinski triangle.