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 P1, P2, …, Pn, but then the number P1P2…Pn + 1 is not divisible by any of P1, P2, …, Pn. If P1P2…Pn + 1 is a prime, then it is a prime other than the originally listed P1, P2, …, Pn; if P1P2…Pn + 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 P1, P2, …, Pn 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.