Fermat Primes and Pascal’s Triangle

If you take the entries Pascal’s triangle mod 2 and draw black for 1 and white for 0, you get a pleasing pattern:

The 2^nth row consists of all 1’s. If you look at the triangle consisting of the first 2^n rows, and take the limit as n \to \infty, you get a fractal called the Sierpinski gasket. This can also be formed by repeatedly cutting triangular holes out of an equilateral triangle:

Something nice happens if you interpret the rows of Pascal’s triangle mod 2 as numbers written in binary:

1 = 1
11 = 3
101 = 5
1111 = 15
10001 = 17
110011 = 51
1010101 = 85
11111111 = 255
100000001 = 257

Notice that some of these rows consist of two 1’s separated by a row of 0’s. These give the famous ‘Fermat numbers‘:

11 = 3 = 2^{2^0} + 1
101 = 5 = 2^{2^1} + 1
10001 = 17 = 2^{2^2} + 1
10000001 = 257 = 2^{2^3} + 1
1000000000000001 = 65537 = 2^{2^4} + 1

The numbers listed above are all prime. Based on this evidence Fermat conjectured that all numbers of the form 2^{2^n} + 1 are prime. But Euler crushed this dream by showing that the next Fermat number, 2^{2^5} + 1, is not prime.

Indeed, even today, no other Fermat numbers are known to be prime! People have checked all of them up to 2^{2^{32}} + 1. They’ve even checked a few bigger ones, the largest being

2^{2^{3329780}} + 1

which turns out to be divisible by

193 \times 2^{3329782} + 1

Here are some much easier challenges:

Puzzle 1. Show that every row of Pascal’s triangle mod 2 corresponds to a product of distinct Fermat numbers:

1 = 1
11 = 3
101 = 5
1111 = 15 = 3 × 5
10001 = 17
110011 = 51 = 3 × 17
1010101 = 85 = 5 × 17
11111111 = 255 = 3 × 5 × 17
100000001 = 257

and so on. Also show that every product of distinct Fermat numbers corresponds to a row of Pascal’s triangle mod 2. What is the pattern?

By the way: the first row, 1, corresponds to the empty product.

Puzzle 2. Show that the product of the first n Fermat numbers is 2 less than the next Fermat number:

3 + 2 = 5
3 × 5 + 2 = 17
3 × 5 × 17 + 2 = 257
3 × 5 × 17 × 257 + 2 = 65537

and so on.

Now, Gauss showed that we can construct a regular n-gon using straight-edge and compass if n is a prime Fermat number. Wantzel went further and showed that if n is odd, we can construct a regular n-gon using straight-edge and compass if and only if n is a product of distinct Fermat primes.

We can construct other regular polygons from these by repeatedly bisecting the angles. And it turns out that’s all:

Gauss–Wantzel Theorem. We can construct a regular n-gon using straight-edge and compass if and only if n is a power of 2 times a product of distinct Fermat primes.

There are only 5 known Fermat primes: 3, 5, 17, 257 and 65537. So, our options for constructing regular polygons with an odd number of sides are extremely limited! There are only 2^5 = 32 options, if we include the regular 1-gon.

Puzzle 3. What is a regular 1-gon? What is a regular 2-gon?

And, as noted in The Book of Numbers by Conway and Guy, the 32 constructible regular polygons with an odd number of sides correspond to the first 32 rows of Pascal’s triangle!

1 = 1
11 = 3
101 = 5
1111 = 15 = 3 × 5
10001 = 17
110011 = 51 = 3 × 17
1010101 = 85 = 5 × 17
11111111 = 255 = 3 × 5 × 17
100000001 = 257
1100000011 = 771 = 3 × 257
10100000101 = 1285 = 5 × 257
101010010101 = 3855 = 3 × 5 × 257

and so on. Here are all 32 rows, borrowed from the Online Encylopedia of Integer Sequences:

Click to enlarge! And here are all 32 odd numbers n for which we know that a regular n-gon is constructible by straight-edge and compass:

1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 65535, 65537, 196611, 327685, 983055, 1114129, 3342387, 5570645, 16711935, 16843009, 50529027, 84215045, 252645135, 286331153, 858993459, 1431655765, 4294967295

So, the largest known odd n for which a regular n-gon is constructible is 4294967295. This is the product of all 5 known Fermat primes:

4294967295 = 3 × 5 × 17 × 257 × 65537

Thanks to Puzzle 2, this is 2 less than the next Fermat number:

4294967295 = 2^{2^5} - 1

We can construct a regular polygon with one more side, namely

4294967296 = 2^{2^5}

sides, because this is a power of 2. But we can’t construct a regular polygon with one more side than that, namely

4294967297 = 2^{2^5} + 1

because Euler showed this Fermat number is not prime.

So, we’ve hit the end of the road… unless someone discovers another Fermat prime.

8 Responses to Fermat Primes and Pascal’s Triangle

  1. Toby Bartels says:

    Puzzle 2 should also begin with a first line involving the empty product: 1 + 2 = 3. (You probably only left that line out to check whether I was reading.)

    • John Baez says:

      I considered it but thought it might confuse some people. You should be be glad to know that at least I felt a pang of guilt for leaving it out!

      • Toby Bartels says:

        You included it in Puzzle 1, so maybe they'll be confused when it doesn't appear this time? I was.

        But I like how this bootstraps the beginning of the Fermat numbers. I say ‘I want a Fermat number!’. You say ‘Well, just multiply together the ones that you have, then add 2.’ (which doesn't work if I obtain them out of order, but never mind that for now). I reply ‘But I don't have any Fermat numbers yet!’, but you reply ‘Don't worry, just do what I said: multiply all none of them together to get 1, then add 2 to get 3.’ and now I've got my first Fermat number out of nothing.

        (As the original version of your comment noted, 1 could itself be considered a non-prime Fermat number, since 1 = 2^{2^0} - 1, but that breaks both puzzles, so let's forbid it.)

      • Toby Bartels says:

        You included it in Puzzle 1, so maybe they'll be confused when it doesn't appear this time? I was.

        But I like how this bootstraps the beginning of the Fermat numbers. I say ‘I want a Fermat number!’. You say ‘Well, just multiply together the ones that you have, then add 2.’ (which doesn't work if I obtain them out of order, but never mind that for now). I reply ‘But I don't have any Fermat numbers yet!’, but you reply ‘Don't worry, just do what I said: multiply all none of them together to get 1, then add 2 to get 3.’ and now I've got my first Fermat number out of nothing.

        (As the original version of your comment noted, 1 could itself be considered a non-prime Fermat number, since 1 = 2^{2^0} - 1, but that breaks both puzzles, so let's forbid it.)

        • Todd Trimble says:

          Ah, but 1 is not a Fermat number anyway, since one should add 1 to a power of 2, not subtract it.

        • Toby Bartels says:

          Of course, and that explains why John deleted that from his comment too! That’s good then, not have even that exception. I was probably mixing up the Fermat numbers F_n = 2^{2^n} + 1 with the Mersenne numbers M_n = 2^n - 1.

          (These also have an associated primality conjecture, that M_n is prime whenever n is, although it's much quicker to see that this is false. And the converse, that n is prime whenever M_n is, is actually true! Since M_0 = 0, this even lets you be perfectly ambiguous about whether to accept 0 as prime.)

  2. vznvzn says:

    am interested in the history of fractals and wonder who 1st called the sierpinski gasket a fractal… the word fractal seems to date mid 20th century but many fractals were discovered earlier, think it would be really great if someone built a comprehensive timeline. anyone up for the challenge? maybe mathworld/ weisstein? btw have found many fractal properties in the collatz conjecture last few yrs, alas few else have noticed, invite anyone to drop by for further discussion :)

    • John Baez says:

      I believe Mandelbrot’s book The Fractal Geometry of Nature has a lot of discussions of early work on fractals, one of the themes being that this work was not considered “serious mathematics”. So that’s where I’d start.

Leave a Reply to Toby Bartels Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.