## Pascal's Triangle using Clock Arithmetic - Part I

Since there is a lot to explore, we will break up this page into sections:

#### When the modulus is a prime

When you use clock arithmetic to form Pascal's triangle there are some very striking visual patterns that can be observed. We will look at some of the simplest first. If we do our arithmetic with modulus 2, and draw the triangle using black squares to rep resent 1 and white squares for 0, we get the following picture:

The next case would be using modulus 3. Since there are three possible values that we could get (namely, 0, 1 or 2), we could draw the triangle using squares of three different colors. We will do that later, but for now we are interested only in where the 0's are, so we will use only two colors, white for 0 and black for any non-zero value. Doing this the "Mod 3" Pascal's triangle looks like:

While we could continue to do this for each of the different possible moduli ( = plural of modulus), the patterns for the prime moduli are the simplest, so we will stick with them for a while. Since you have already worked out Pascal's triangle mod 5, you can do this restricted coloring to get the pattern of the 0's for it and you might want to work out the same thing mod 7 before looking at the results below.

#### Zero Patterns for Pascal's Triangle

The basic "building block" of these patterns (for prime modulus) is the triangle formed by the first p^2 + 1 rows (that is, p squared plus 1), from row 0 to row p^2, where p is the prime modulus. So, for p = 2, it will be rows 0 to 4 , for p = 3, it will be rows 0 to 9, and so on. Each of these building block triangles has a number of small white triangles in it. For p = 2 there is only one (we'll think of the single white square as a triangle to be consistant), for p = 3 there are 3 of them. How many are there for p = 5 and p = 7? Do these numbers look familiar? How many do you think there will be for p = 11? (Hint: Look in the normal Pascal triangle).

Once you have identified a building block, you can make really large triangles without having to do a lot of calculations. Look at the building block for the mod 3 triangle. Besides the 3 small white triangles, there are 6 small black triangles in this bu ilding block. We can make a bigger mod 3 triangle by taking 6 copies of the building block triangle and arranging them so that their positions relative to one another are the same as the 6 small black triangles in the original building block (you can thin k of this as replacing each small black triangle with a copy of the building block).

Try doing this with the p=2 and p=5 building blocks. This process can b e repeated ... that is, for the p=3 case, you can take 6 copies of the large triangle that is made up of building blocks, and arrange them in the positions of the 6 small black triangles of the original building block. You can try to do this a couple of t imes with the p=2 example (the others get so large so fast that you wouldn't be able to do it more than once by hand).

#### When the modulus is a power of a prime

We'll now look at some related triangles. Consider the triangles we get with moduli 2, 4, 8, ... . When a position in say, the triangle with modulus 8, is colored white, that means that the binomial coefficient of that position is evenly divided by 8. But if a number is evenly divided by 8, it must also be evenly divided by 4 and by 2. That means that this same position will be white in both the triangle with modulus 4 and the triangle with modulus 2. Similarly, if a position in the triangle with modulus 2 is black, then the binomial coefficient is not evenly divided by 2 (that is, it is an odd number), and so it can not be evenly divided by 4 or 8 or any higher power of 2. Thus, if a position is black in one of these triangles, it will remain black in al l the triangles whose modulus is a higher power. So, if we compare the triangles with modulus 2 and 4 and then the triangles with modulus 4 and 8, what we will see as we move up in the size of the modulus is that all the black squares remain black and the n some of the white squares become black and then stay that way. To see this progression, we'll look at the mod 2 triangle and color the squares that become black in the mod 4 triangle in red and those that become black in the mod 8 triangle in blue.

You should try to do the same thing for the mod 3, mod 9 and mod 27 triangles (caution: you won't be able to draw enough of the mod 27 triangle to see its full pattern).

To see what is happening when we go from one of these triangles to the next higher power triangle, we'll look very carefully at the mod 2 and mod 4 examples. Go back and look at the mod 2 triangle. We can view it abstractly as a collection of white triang les of different sizes in a black background (remember that we are thinking of those single white squares as triangles for this example). We will number the sizes of the white triangles. The smallest triangle, of size 1, will be the single white square in the center of a building block. The next largest triangle, of size 2, is the white triangle in the center when you put three building blocks together. To describe the larger sizes we need to expand our vocabulary about building blocks. Let's say that a s ingle black square is a block of order 1. A triangle made up of three black squares is a block of order 2. A triangle made up of three blocks of order 2 is a block of order 3 (this is the building block for the mod 2 Pascal's triangle ). A triangle made up of three blocks of order 3 is a block of order 4. In general, a triangle made up of three blocks of order n is a block of order n+1. Now the white triangle of size 2 is the one in the center of a block of order 4, using our ne w language. A white triangle of size 3 will be the one in the center of a block of order 5. In general a white triangle of size k is in the center of a block of order k+2.

Now, to go from the mod 2 triangle to the mod 4 triangle, we know that we will be turning some of the white squares (squares that are inside of white triangles) into black squares, and what we need is a rule for doing this. It turns out that the rule is v ery simple, but the result looks very complicated. For each white triangle of size at least two (these are pointed down), dissect the triangle into 4 equal triangles. There will be one triangle in the middle (it will be pointed up) and the other three on its sides (all of them pointed down). The rule is that in a white triangle of size n, you replace the middle triangle of the dissection with a block of order n. To make this clear, I've only done the replacements in triangles of sizes 3, 4 and 5 in the di agram below.

Since we can't dissect a triangle of size 1, we'll have to think of it's "middle" as being the whole triangle. The rule then does not have to be changed for triangles of size 1, we just replace them by a block of order 1 (that is, we will fill in the whit e square). Here is the same diagram with all the replacements being done, giving the mod 4 triangle (think of all the colors as black).

You should try to see how you would get from the mod 4 triangle to the mod 8 triangle using these ideas, before you look at the answer. ( mod 8 triangle )

Now, let's look at the mod 3 and the mod 9 triangles to see what changes we have to make. The first thing we notice is that in the building block for the mod 3 triangle, there are 3 white triangles (the mod 2 building block had only one white triangle in it). We will still want to call these white triangles, triangles of size 1. Putting 6 of these building blocks together (in the places of the black triangles of the building block), we get the next larger size block which contains 3 white triangles of siz e 2. To keep the same relationship between block orders and triangle sizes as we had in the mod 2 example, we must remember that we will now need 6 blocks to make the next order block and if a block has order k then it contains 3 white triangles of size k -2. Here is what the block orders and triangle sizes look like.

We now need the rule for filling in the white triangles. In the mod 2 example, we dissected the white triangles into 4 triangles and filled the middle one (the one pointed up) with a block. This time, we need to dissect the white triangles into 9 triangle s and fill all the ones pointing up with blocks (there will be three of them). With this understanding, the rule stays the same, we fill a white triangle of size k with blocks of order k. This is what filling a white triangle of size 3 looks like:

To finish up, we only have to consider what to do with triangles of size 1 since they can not be divided into 9 pieces. As before, we will just fill these triangles with 3 blocks of size 1, making the triangle disappear. So, the final result looks like th is:

Starting with the mod 9 triangle, how do you think you would make the mod 27 triangle?

Can you figure out what the blocks and filling rule will be when you go from the mod 5 triangle to the mod 25 triangle?

#### When the modulus is composite

When the modulus can be divided by more than one prime number (making it a so-called composite number), the picture looks very complicated, but, as we shall see, given the work we have already done, they are quite simple to make.

Let's look at the simplest example, the mod 6 triangle. Since 6 = 2 x 3, if a position in the mod 6 triangle is white that means that the corresponding binomial coefficient is divisible by 6 ... so it must also be divisible by 2 and by 3. This means that the same position in the mod 2 triangle and in the mod 3 triangle must also be white. If a position in either of the "smaller" triangles is black, then that position in the mod 6 triangle must be black as well, since the binomial coefficient is either not divisible by 2 or by 3, and so, it can not be divisible by 6. This means that if we took copies of the mod 2 triangle and the mod 3 triangle and placed one on top of the other, the only white squares that appear are those where the corresponding binomial coefficient is divisible by both 2 and 3, i.e., by 6. This will give us the mod 6 triangle. To actually do this, it might be easiest to draw the triangles (using the same size squares) on two pieces of transparent film, and then slide one over the other . The result should look something like this:

For more complicated moduli, we first factor the modulus into its prime factors and group all the factors of the same prime together. For instance, 180 = 2 x 2 x 3 x 3 x 5 = 4 x 9 x 5. This is called the prime factorization of a number. Then for ea ch prime power in our expression, we take the corresponding Pascal's triangle and place them on top of one another. So, if we wanted the mod 180 triangle, we would take the mod 4 triangle, the mod 9 triangle and the mod 5 triangle and put them one on top of the other. Here is another example. To form the mod 12 triangle, we write 12 = 3 x 4, and place the mod 3 triangle on top of the mod 4 triangle. The result looks like this:

Try to construct the mod 10 triangle before looking at it.( mod 10 triangle )