Add new comment

Maths in a minute: How many primes?


Euclid of Alexandria

Primes are natural numbers that are only divisible by themselves and 1. The first few examples are $2$, $3$, $5$, $7$, and $11$. And the good news is that they go on forever. No matter how far you move up the number line there'll always be another prime ahead of you. The fact that there are infinitely many primes was already known to the ancient Greeks. Here's a proof, attributed to the most famous Greek mathematician of them all, Euclid (although he didn't use quite the same language and concepts as we do today).

Suppose that there are only finitely many primes. We can label them $p_1$, $p_2$, $p_3$, etc, up to $p_ n$, the very last prime. Now define the number

  \[ P = p_1 \times p_2 \times p_3 ... \times p_ n+1. \]    

As an example, if there were only five primes $p_1=2$, $p_2=3$, $p_3=5$, $p_4=7$, and $p_5=11$, then we’d have

  \[ P = 2 \times 3 \times 5 \times 7 \times 11 +1 = 2311. \]    

Now, if $P$ is itself a prime number (as it is in our example), then clearly it can’t be one of the primes in our list: that’s because it’s bigger than all of them. If $P$ is not prime, then, like any other natural number, it can be written as a product of primes. Let’s pick one of the primes that divides $P$ and denote it by $p$. Now $p$ cannot be any of the primes $p_1$ up to $p_ n$ because if it was, then it would divide

  \[ P - (p_1 \times p_2 \times p_3 ... \times p_ n) = 1, \]    

which is impossible because $1$ is not divisible by any natural number. Therefore the collection $p_1$, $p_2$, $p_3$, etc, up to $p_ n$ cannot contain all of the primes as we had assumed. This contradiction means that there must be infinitely many primes.

You can read more about prime numbers and number theory on Plus.

Read more about...

Filtered HTML

  • Web page addresses and email addresses turn into links automatically.
  • Allowed HTML tags: <a href hreflang> <em> <strong> <cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.
  • Want facts and want them fast? Our Maths in a minute series explores key mathematical concepts in just a few words.

  • What do chocolate and mayonnaise have in common? It's maths! Find out how in this podcast featuring engineer Valerie Pinfield.

  • Is it possible to write unique music with the limited quantity of notes and chords available? We ask musician Oli Freke!

  • How can maths help to understand the Southern Ocean, a vital component of the Earth's climate system?

  • Was the mathematical modelling projecting the course of the pandemic too pessimistic, or were the projections justified? Matt Keeling tells our colleagues from SBIDER about the COVID models that fed into public policy.

  • PhD student Daniel Kreuter tells us about his work on the BloodCounts! project, which uses maths to make optimal use of the billions of blood tests performed every year around the globe.