A “new to me” proof that there are infinitely many primes

Last evening I saw Patrick Honner link to a Richard Green post discussing a prime number theorem he saw on Cut the Knot’s website:

So, thanks to Patrick Honner for pointing out Richard Green’s post, thanks to Richard Green for a great post and also for pointing out the Cut the Knot piece, and thanks to Alexander Bogomolny for maintaining the amazing Cut the Knot site.

By chance I’m between chapters in our Introduction to Geometry book with my older son, and since he’s going on a short trip today I didn’t want to start talking about circles just yet. This “new to me” proof that there are infinitely many primes was perfect for a discussion today.

Both Green’s piece and the Cut the Knot piece show how delightful this proof is, but there’s a lot going on in the background – especially when you are trying to talk through the ideas with a kid. We spent about 45 minutes going through things slowly and then started in again with the camera on.

First up, an introduction to the problem and my son discussing the “standard” proof that the number of primes is infinite:


Next up, we begin to dig into one of the critical ideas in the proof – the factorization of the polynomial x^4 + x^2 + 1, and the idea that the two polynomial factors will never have common factors when x is an integer. The factorization idea relies on the Euclidean algorithm.


The next step is looking at how we construct the sequence of numbers that have progressively more prime factors. I was trying to talk through this part of the proof without referring to mathematical induction, but if a student is familiar with that concept, there’s probably an easier way to explain this portion of the proof.


Finally, a last little discussion of how the powers of 2 help us construct the sequence of numbers we are looking for. Sorry we went off camera a little bit on this part – I didn’t realize the camera was zoomed in so much. One small point about exponents confused my son a little, but once we got past that little hiccup I think he was able to get his arms around how we walk down the path of creating the sequence of integers.


This project made for a really fun morning. I like how some basic ideas from math come into play – prime factorization, factoring polynomials, and the Euclidean algorithm, for example. I also really like the idea of seeing a known result from a completely new angle. Seems like a really great example for kids interested in learning about proof and mathematical thinking in general. Thanks again to Patrick Honner, Richard Green, and Alexander Bogomolny for the inspiration.



2 Comments so far. Leave a comment below.
  1. It seems that the fun idea is constructing a sequence where the nth term has at least n distinct prime factors.

    If so, then I don’t understand what this particular polynomial adds. Since we just want two coprime polynomials, a simple choice is X and X+1, though perhaps that’s not interesting because it is basically just a restatement of the “standard” proof?

    • The relationship between x^4 + x^2 + 1 and the factor x^2 + x + 1 allows you to explicitly construct the sequence:

      7, 21, 273, 65793, 4295032833, . . . .


      In which one term is (i) always divisible by the prior term, and (ii) always has prime factors that not factors of the prior term.

      So the nth term always has at least n+1 prime factors.


One Trackback

Leave a 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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: