Divisibility and PrimesThe Distribution of Primes

The easiest way to check if a number is prime is to try to divide it by all smaller integers. Computers can do this very quickly and efficiently. For very large numbers, with hundreds of digits, there are also more efficient algorithms. Some of these even use probability to determine if a number is almost certainly prime.

Here is a calculator that allows you to check if any number is prime:

Calculating these large prime numbers might seem like just a waste of time, but later in this course you’ll learn about various real life applications where computers have to use large primes.

Here you can generate your own prime numbers with a given number of digits:

The Ulam Spiral

The Polish mathematician Stanisław Ulam came up with a cool way to show the distribution of large prime numbers, while doodling during a “long and very boring” meeting in 1963.

We write down all integers in a rectangular grid, starting with 1 in the middle and then spiralling outwards. Then we highlight all numbers which are prime.

So far, the Ulam spiral doesn’t look particularly exciting. But if we zoom out, interesting patterns emerge. Here are the primes up to 160,000:

The Goldbach Conjecture

In 1742, the German mathematician Christian Goldbach made a curious discovery: he noticed that all even integers (except 2) can be written as the sum of two prime numbers. For example, 8 = 5 + 3 and 24 = 13 + 11. This is quite surprising, because primes are defined using multiplication and factors – and shouldn’t have much to do with addition.

Goldbach wrote about his observation in a letter to the famous mathematician Leonhard Euler, but neither of them was able to prove it. It became known as the Goldbach Conjecture.

Computers have checked that the Goldbach Conjecture works for every even number up to 4 × 10¹⁸ (that’s a 4 with 18 zeros), but mathematicians have still not found a proof that it works for all even integers. And that is a big difference, because there are infinitely many integers, so we couldn’t possibly check all of them.

Its apparent simplicity made the Goldbach conjecture one of the most famous unsolved problems in mathematics.

Twin Primes

We have already seen that prime numbers get more spread out as they get bigger. But they always seem to appear completely random, and occasionally we find two primes right next to each other, just one number apart: these are called Twin Primes.

35,1113,4143,101103,20272029,108,377108,379,1,523,6511,523,653

The largest known pair of twin primes has an incredible 58,711 digits! But are there infinitely many twin primes, just like there are infinitely many primes? Nobody knows – the Twin Prime conjecture is another one of the many unsolved problems surrounding the primes.

The Riemann Hypothesis

Mathematicians have spent many centuries exploring the pattern and distribution of prime numbers. They seem to appear completely randomly – sometimes there are huge gaps in between consecutive primes, and sometimes we find twin primes right next to each other.

When only 15 years old, the German mathematician Carl Friedrich Gauss had a groundbreaking new idea: he counted the number of primes up to a certain point, and showed the results in a chart:

Along the x-axis you can see all integers. Whenever there is a prime, the Prime Counting Function (shown in blue) increases by one. As we zoom out, the blue line becomes very smooth. Gauss noticed that the shape of this function looks very similar to the function xlogx (shown in red). He predicted that the two functions are always “approximately similar”, and this was proven in 1896.

However, as you can see above, there is still a significant error between the actual number of primes, and Gauss’s approximation. In 1859, the mathematician Bernhard Riemann discovered an approximation that looked much better, but he wasn’t able to prove that it would always work. His idea became known as the Riemann Hypothesis.

Hundreds of mathematicians have tried to prove Riemann’s hypothesis, but all without success. It is often considered one of the most difficult and most important unsolved problems in mathematics. In 2000, the Clay Mathematics Institute named it one of seven Millennium Prize Problems and promised $1,000,000 to any mathematician who solves it.