# Pascal Triangle and Prime Numbers

My question @ StackOverflow just got closed as not programing related so I'm posting here.

Please refer to the question @ SO, since:

• sorry, new users can only post a maximum of one hyperlink
• sorry, new users aren't allowed to use image tags

[Edited to include enough links and images by GJK.]

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?

-
Here is a starting point: en.wikipedia.org/wiki/Lucas'_theorem –  Reid Barton Dec 17 '09 at 16:44
The quote messes things up in Reid's comment. For primes, the pattern that you found was published by Edouard Lucas in 1878. It is not hard to make a calculation for composite numbers, but Lucas made the point that the answer is much nicer for primes. en.wikipedia.org/wiki/Lucas_theorem –  Greg Kuperberg Dec 17 '09 at 17:03
If and only if n is a prime, the n'th row will be all highlighted. Can't this be used to test the primality or is it too slow? –  Alix Axel Dec 18 '09 at 16:45
It's far too slow. Nobody knows an effective method to compute factorials. (A related result along these lines is Wilson's theorem, which is also useless as a primality test: en.wikipedia.org/wiki/Wilson%27s_theorem). –  Qiaochu Yuan Dec 29 '09 at 9:14

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!

-
Thanks, that is a bunch of very cool information. =) –  Alix Axel Dec 17 '09 at 17:13
If you know what happens for powers of primes, then you can figure out what happens for any number; the binomial coefficients divisible by, say, 36 are just those divisible by both 4 and 9. –  Michael Lugo Dec 17 '09 at 17:16
I just realized that my added paragraph also explains why composites are not as nice as primes. For p prime, if p^m is the largest power that divides a and p^n is the largest power that divides b, then p^(m-n) is the largest power that divides a/b. But this isn't true in general for composites! Think about 1000/250, for example. The key is that divisibility by 10 is dependent on divisibility both by 2 and by 5, and we have the freedom to mess around with one of those without changing the other. –  Harrison Brown Dec 17 '09 at 17:17
Dmitry Fuchs mentions a congruence that implies that $\binom{ap^n}{bp^n}$ converges $p$-adically as $n \to \infty$. It's a good question to understand what this $p$-adic limit could mean. mathcircle.berkeley.edu/BMC6/ps0405/binom.ps –  Greg Kuperberg Dec 17 '09 at 18:58
@Greg Kuperberg: Looking at the link I see that problem 10 is attributed to you, and it mentions that (whenever this was written -- when was this written?) we knew of two primes with a certain property, and you thought the third was out of reach. Do we know the third yet? :P –  Harrison Brown Dec 17 '09 at 19:28

The mod 2 case is related to the Sierpinski triangle.

-

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= pa 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.

-

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

-
Definitely not original, but definitely fun, and closely related to my answer. The different thing with composite numbers is that your solution depends on the equation: (# of times p divides a/b) = (# of times p divides a) - (# of times p divides b), which is true when p is prime but not if p is composite. (Again, take p = 10, a = 1000, b = 250.) –  Harrison Brown Dec 17 '09 at 18:11
Your K(X,p) is also (X - (sum of the digits of X base p))/(p-1). So, the number of times p divides M choose N is the number of carries you perform when you add N to M-N base p. That makes it clear how many entries of the Mth row of Pascal's triangle are not divisible by p, and which ones. –  Douglas Zare Jan 15 '10 at 18:21

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 phenomenom.

-
I once carefully drew the triangle as far as $\left( \begin{array}{c} 16 \\\ \ast \end{array} \right)$ in an effort to show visually how many gifts were given by day $n$ in the Twelve Days of Christmas song. I was delighted to find the consecutive values 1001, 2002, 3003 in the $\left( \begin{array}{c} 14 \\\ \ast \end{array} \right)$ row. I do not think the values $a, 2a, 3a$ can occur all that often in a row next to each other, for one thing $2 a$ must lie very near the inflection point of the approximating multiple of a Gaussian distribution curve. But note primes 7,11,13. –  Will Jagy May 14 '10 at 19:26
${n\choose r}=2{n\choose r-1}$ is equivalent to $n=3r-1$, and ${n\choose r+1}=(3/2){n\choose r}$ is equivalent to $2n=5r+3$, so the only way to get $a,2a,3a$ as consecutive entries in a row of Pascal's triangle is the one that delighted you, corresponding to the solution $n=14$, $r=5$ of that pair of linear equations. –  Gerry Myerson Jun 30 '10 at 5:22

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.

-