Search This Blog

08 December 2006

Pascal's Triangle and Prime Numbers

We start off using a basic Pascal Triangle....

If you aren't familiar with how it is constructed, the rules are quite simple... A) anywhere that is blue here is considered "0". B) Start with a "1" at the top. C) For each spot, simply add the two spots above it.

Now that we have the numbers, the next step is to mod them. If you are unfamiliar with "mod", think of it as "the remainder after division"... Thus, 10 mod 3 is 1 (10/3 = 3r1) and 10 mod 2 is 0 (10/2=5r0).

To simplify matters, all we care about is when the remainder is 0. For example, in this version of our Pascal's Triangle, we color coded in a darker blue anything that has a remainder other than 0. Anotherwords, the ones NOT colored in are MULTIPLES of 2.

One thing you will notice is that it is a fractal (known as Sierpinski's Gasket)... Basically, we have a 2x2 (2 high, 2 wide at base) triangle colored in... Then we repeat by adding 2 of those triangles to the bottom. So, in this example, the original triangle has 1 on row#0 and 1,1 on row#1. The two repeats are row#2 and row#3, and incidentally both contain the numbers 1 on row#2 and 1,3 (or 3,1) on row#3. The second copy is a mirror of the first.

Then, grab everything (original and two copies) and copy them as a group [thus the fractal] two more times.

The mod3 version (colored in red for NON-multiples of 3) shown here is similar with a slight difference. In this case, the original is 3x3.

But the real tricky part is the copying/cloning... While the first two clones (1/ 1,4 / 1,6,10) must seem like the exact same pattern as before, notice that we now make 3 more copies in the next couple rows BEFORE we group and clone.

This can be easily understood. Look back at the original triangle in mod2. Notice one entry in first row, and two entries in the second? When we clone it, we clone the one at the top twice beneath it.

Now look at the original triangle in mod3. The original has one in the top row, two in the second, and three in the third. We copy the original top one twice into our second set of rows, and three times in the third set of rows... THEN we group and repeat.

Let's take a look at another aspect... Notice the upside down "empty" triangles in the middle? For example, on mod2, row#8 through row#14? Well, what you will actually see is that at 21, 22 and 23 that only the edge "1"s are colored in... That is because those rows are POWERS of 2. Similarly you see the same on 31 and 32 ( further isn't shown in this image )... This will actually become very important soon.

Now, let's consider what happens when we overlay them... I like to think of this like transparencies in elementary school (actually, I even bought some transparencies for this very purpose)...

The first thing you will likely notice is that some of those show blue, some show red, some show a purplish mix.

The blue ones are NOT multiples of 3 (cuz they show blue) but ARE multiples of 2 (because it would have been clear/empty on the mod2 chart).

The red ones would be multiples of 2 but NOT multiples of 3, for the same reason.
The purple ones are not multiples of 2 OR 3.
The clear/empty ones are therefore both multiples of 2 AND 3.

Let's look at some of those numbers... In the first 9 rows (0-8) the only clear/empty ones are the number 6, which is incidentally the 2*3. Then we also see 36, 12, 120.... You get the picture...

So why is this important? Well, for a couple reasons...

First, it shows that all composite numbers are actually transparent overlays of their prime factors...

Second, and this one is important, is because it also shows us what those factors are :)

How? Well, let's take a PQ value of 6 for example. Sure, off the top of our head, we know it is 2*3, but let's LOOK at it. Specifically, let's look at the row#6...

Now, what are those entries mod (2*3) [ie: mod6]?
Ok, you see what we got here? Col#2 has a value of 3. Col #3 has a value of 2. The only other non-zero entries are the mirror of these, and the 1s at the end. That is going to be true for ALL PQ where P and Q are prime.

I'll do more on this later.
Post a Comment