Pascal triangle and prime numbers

Question

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?

Answer 1

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!

Answer 2

The mod 2 case is related to the Sierpinski triangle.

Answer 3

When considering the divisibility of binomial coefficients, it is very instructive to also look at q-binomial coefficients.

The q-bimonal coefficient are polynomials in q defined by the formula ${{\textstyle a} \choose {\textstyle b}}_q = \frac{{\textstyle a}\underset{\textstyle .}q}{{\textstyle b}\underset{\textstyle .}q{\textstyle (a-b)}\underset{\textstyle .}q}$,
where ${\textstyle n}\underset{\textstyle .}{\scriptstyle q}:=(1-q)(1-q^2)(1-q^3)\ldots (1-q^n)$ denotes the q-factorial. They satisfy ${{\textstyle a} \choose {\textstyle b}}_q | _ { q = 1 } = {{\textstyle a} \choose {\textstyle b}}$.
The symbol is a "q" with a dot under it, to remind us of the "!" symbol. It's maybe not the most standard notation, but I find it irresistibly cute. See here for a more detailed exposition, with somewhat more standard notations.

Just like integer numbers can be factorized into primes, polynomials can be factored into irreducible polynomials. The polynomials that occur in the factorization of quantum binomial coefficients are the so-called cyclotomic polynomials φ_n(q), of which there is one for every natural number n. For your problem, the relevant fact about cyclotomic polynomials is that φ_n(1) is easy to compute. It's p when n= p^a for some prime numer p, and it's 1 otherwise. So if you have a factorization of some q-binomial coefficient into cyclotomic polynomials, you can deduce the prime number factorization of the corresponding usual binomial coefficients by plugging in q=0.

Now, unlike for the usual binomial coefficients, the factorization of q-bimonal coefficient is multiplicity-free: no exponents! Moreover, it is much more easy to determine when φ_n divides ${{\textstyle a} \choose {\textstyle b}}$: that happens if and only if (remainder of b modulo n) + (remainder of (a-1) modulo n) + 1 < n. The latter condition corresponds to a pattern of triangles that is much more regular than the pictures you posted above. You obtain your picture by superimposing the various patterns I just described.

Answer 4

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.

Answer 5

Looks like some people already came up with some better answers, so I'll just quickly mention that you may like solving problems on ProjectEuler.net as some of the problems are right up this way of thinking.

For one of the problems I created the following way to determine the number of times p divides M choose N:

M!/(N!*(M-N)!)
K(M,p)-K(N,p)-K(M-N,p)
Where K(X,p) is the number of times p divides X! and is equal to:
K(X,p)=Floor(X/p)+Floor(X/p^2)+Floor(X/p^3)+...

(Quick explination: Even for each p^2 bellow X there are two factors of p added to the product, but one was already counted in Floor(X/p), so we just add the extra one for the new power of p)

Probably not original, but it was fun to come up with it.

Dan

Answer 6

Considering the "Pascal Triangle as an integer" phenomenon (can be found on google)... and that I cannot calculate or be sure that this answer is proofed... If lines of Pascal's triangle are a test for primes Then ... (maybe) you can just get and test line N this way: Using arbitrary precision integer arithmetic, in base N, calculate N to the power of (1000 to the power of the number of digits in the catalan number, plus 1), remembering that the 1000+1=10...01 is in base N and there must be an even number of zeroes in it.

Arbitrary precision integer arithmetic powers can be done easily in Binary when the Binary Multiply algorithm uses shift-and-multiply instead of shift-and-add. But don't be confused by this "easy powers" method... because it should be done in Base N, and the phenomenon suggested to search for can produce all powers with a single fraction in any base, and makes P-Triangle as if it were the powers of 11 in ANY arbitrary integer base. Which way is faster should decide which way to calculate it.

The calculation will sooner or later produce the line N, in Base N, and you will know N is prime if the Number calculated as line N has 1 followed by N and multiples of N, separated by zeroes. Simple example: 100001 to the power of 7 should be 1000070002100035000210000700001. (Base 10) Obviously I overestimate the number to raise to the N for prime testing because the carries are to be avoided, and there Must be even zeroes inside the "11", and I can't guess at the moment how much precision would be needed. I should have used base 7 as the example, and if I did, you would get the obviously prime-proven result like 1001 to power 7, base 7 = 1010030050030010001, which nice and neatly, I think, proves it prime, since multiples of 7, base 7 are multiples of "10". (1,10,30,50,30,10,1 in properly aligned orders of magnitude per binomial coefficient)

I am speaking for the discoverer of the phenomenon.