co.combinatorics - 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 here.

What the p-adic numbers do is help you get around the following obstacle: Say you want to tell whether a quotient of two numbers, a/b, is divisible by p. (We'll assume for now that 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 a/b is; if a isn't divisible by p, then of course 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 p^2. Or that a is divisible by p^17, and b is divisible by p^14 but not p^15. You see how this gets confusing! The p-adic absolute value encodes this sort of information for you.

This also mentions 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 this wonderfully-titled paper.

Hope this helps!