Euclid’s Proof of the Infinitude of Primes


So a few weeks ago my younger sister asked me what the biggest prime number was. I was getting prepared to explain Euclids proof to her… when I realised that she probably doesn’t care and also didn’t exactly need to know about it, instead I just told her that “it’s a pretty large number”. Truth is, there is no largest prime number as much as there is no largest number. Euclid proved this in around 300 BC, which is also the oldest known proof that there are infinite number of primes.

Euclid started by looking at the known primes and adding one to their product. For example both 2 and 3 are primes: their product plus 1 is also a prime: 2*3+1=7. Continue by adding 5 to the same process: 2*3*5+1=31 – and voir la, that is a prime too. The nice but not beautiful thing about this is that sometimes this algorithm will churn out primes and sometimes it will not!

Here is another way of looking at it:

Suppose that p1=2 < p2 = 3 < … < pr are all of the primes. Let P = p1p2pr+1 and let p be a prime dividing P; then p can not be any of p1p2, …, pr, otherwise p would divide the difference Pp1p2pr=1, which is impossible. So this prime p is still another prime, and p1p2pr would not be all of the primes

Although Euclid did not find the way to using this procedure to find only primes, he did find that this can be used to show that there is infinitely many primes.

Nadzia Laskar

This entry was posted by dailysliceofpi.

Leave a Reply

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

You are commenting using your 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: