Prime numbers

 

1. Introduction

Most people consider integers to be the most fundamental numbers, and all other numbers are built up upon them. However, there is another view from mathematicians. Every integer greater than 1 is either a prime or a product of primes. Therefore they regard prime numbers to be the most fundamental composition of numbers. Some ancient Chinese mathematicians called prime numbers ‘math root’, meaning the fundamental basis of mathematics.

The branch of mathematics which concentrates on the study of the properties of integers is known as number theory. The study of prime numbers plays a central role in this field.

 

2. The Sieve of Eratosthenes

To study primes, we first need to find a way of identifying them. The Greek mathematician Eratosthenes found a way of doing so about 2000 years ago. He fixed a sheet of goat skin on a frame and listed the natural numbers on the sheet. He then removed the multiples of 2, 3, 5, etc with a knife and got a list of the first few prime numbers. People call this method the sieve of Eratosthenes, because the sheet of goat skin acts like a sieve which allows the composites to pass through and retains the primes. However, using such method to identify prime numbers is tedious and highly inefficient.

3. The Infinitude of Primes

Soon after the sieve of Eratosthenes was invented, there was a debate among the Greek mathematicians on whether there are infinitely many primes.

One day, Euclid, a professor at the University of Alexandria, found a simple proof that answers the question positively. He realised that if there were only finitely many primes, then we can list out all of them, say P₁, P₂, …, P_n, but then the number P₁P₂…P_n + 1 is not divisible by any of P₁, P₂, …, P_n. If P₁P₂…P_n + 1 is a prime, then it is a prime other than the originally listed P₁, P₂, …, P_n; if P₁P₂…P_n + 1 is composite, then there must be a prime dividing it, but this prime would have to be outside our original list of prime numbers. In either case P₁, P₂, …, P_n cannot be the full list of all prime numbers, which is a contradiction. Thus we have proved that there must be infinitely many primes.

 

4. The Prime Spiral

It would be great if we could discover a formula that generates all the prime numbers. However, one could imagine that this is no easy task as the distribution of primes is too irregular to fit into a formula.

In 1963, the American mathematician Ulam attended a boring talk in a mathematical conference. He amused himself by drawing a chessboard on a piece of paper and intended to play chess against himself. While drawing a grid of lines, he decided to number the intersections according to a spiral pattern, and then began circling the numbers in the spiral that were primes. He would like to see whether there would be some patterns.

Surprisingly, the circled primes appeared to fall along a number of diagonal straight lines. This motivated him to repeat the experiment on a computer. He did the same thing for the spiral from 1 to 65000, and the same phenomenon remained. This is known as the prime spiral. This is an interesting discovery which helped the study of primes later on.

100	99	98	97	96	95	94	93	92	91
65	64	63	62	61	60	59	58	57	90
66	37	36	35	34	33	32	31	56	89
67	38	17	16	15	14	13	30	55	88
68	39	18	5	4	3	12	29	54	87
69	40	19	6	1	2	11	28	53	86
70	41	20	7	8	9	10	27	52	85
71	42	21	22	23	24	25	26	51	84
72	43	44	45	46	47	48	49	50	83
73	74	75	76	77	78	79	80	81	82

The Prime Spiral

 

5. The Prime Number Theorem

In 1800, two great German mathematician Gauss and Legendre came up with an important conjecture independently from observing tables of the following kind.

x	p(x)
103	168	145	0.01680
104	1229	1086	0.01229
105	9592	8686	0.00959
106	79498	72382	0.00795
107	664579	620421	0.00665
108	5761455	5428681	0.00576
109	50847478	48254942	0.00508

In the table, p(x) represents the number of primes not exceeding x, while ln x is the natural logarithm of x. They found that p(x) increases as x increases, while the ratio decreases as x increases. Furthermore, p(x) comes close to as x increases. This is the famous Prime Number Theorem: the ratio between p(x) and tends to 1 as x tends to infinity.

Since both Gauss and Legendre failed to give a proof, this was only called the “prime number conjecture” or the “Gauss-Legendre conjecture” at the beginning. Nevertheless, it was already great for discovering such a simple relationship between the discrete quantity p(x) and the continuous quantity .

It is not until 1894 that the prime number conjecture was eventually proved by the French mathematician Hadamard. Two years later, De la Vallée Poussin proved the same conjecture independently. Then the name of the celebrated prime number theorem was eventually established.

It is of course a great breakthrough to have the prime number theorem proved, but mathematicians were still not satisfied as the proof involved advanced techniques in complex analysis, especially when the statement of the theorem is so elementary. They reckoned that the use of such advanced mathematics is not necessary, so they began the search for an “elementary” proof of the prime number theorem. In 1949, two young mathematicians, Selberg and Erdös, one from Norway and one from Hungary, eventually found an elementary proof of the prime number theorem. In both of their proofs, they used an important Selberg inequality, and the importance of this inequality has even outweighed the fact that an elementary proof had been found.

Selberg was not only known for having proved the prime number theorem. He was probably better known for contributing to the proof of the Riemann hypothesis. Because of this, he won the Fields Medal — the greatest honour in the mathematical world — on the 11th International Congress of Mathematicians held in Cambridge, USA in 1950.