Back in the days when I was in high-school I developed a big interest about number theory specifically prime numbers and prefect numbers, I used to stay awake all night long with a bunch of sketch papers trying to come up with a formula to generate / test prime numbers. I discovered a lot of things by my own like $p(p + 1)/2$ is a perfect number when p is a Mersenne prime.
I was so obsessed back then that I used to make mental calculations when I was asleep, I remember one day waking up really excited because I had discovered that $2^p – 2 = 0 \pmod p$ when $p$ is a prime, only to discover a few weeks later that Pierre de Fermat had a similar idea but, unfortunately it didn't work for pseudoprimes. I was very disappointed back then and I started playing with the Pascal triangle.
Blaise Pascal, Marin Mersenne and Pierre de Fermat were contemporaneous and shared thoughts with letters, in fact if you think a bit both the Mersenne prime formula and the Fermat primality test seem to be closely related with the rows of the Pascal triangle (the sum of all numbers in row $n$ is $2^n$ where the first and last numbers are $1$, hence the $-1$ in the Mersenne formula and $-1$ or $-2$ in the primality tests).
I coded a Pascal Triangle generator with PHP and HTML that highlighted all the numbers that were multiples of a specific number and the results amazed me, and until this day I don't know why this happens and I would very much like to know why. Instead of trying to explain, I'll post here the images.
Composite Example:
Prime Example:
I think the difference [between the prime and composite cases] is obvious, but if you're confused just say so and I'll try to go into it a bit more…
Can anyone explain me why does this happens?
Best Answer
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!