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.

This entry was posted on Tuesday, February 5th, 2019 at 5:53 pm and is filed under mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

8 Responses to Fermat Primes and Pascal’s Triangle

  1. Toby Bartels says:
    6 February, 2019 at 5:23 am

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

    Reply
    • John Baez says:
      6 February, 2019 at 7:14 am

      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!

      Reply
      • Toby Bartels says:
        6 February, 2019 at 10:57 am

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

        Reply
      • Toby Bartels says:
        6 February, 2019 at 10:58 am

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

        Reply
        • Todd Trimble says:
          6 February, 2019 at 1:04 pm

          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:
          6 February, 2019 at 8:52 pm

          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:
    8 February, 2019 at 4:37 am

    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 :)

    Reply
    • John Baez says:
      8 February, 2019 at 7:32 am

      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.

      Reply

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

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