![[Zimaths article logo]](artic.gif)
A prime number p is a positive integer (not 1) that is only divisible by 1 and p. The set of primes is therefore 2, 3, 5, 7, 11, .... Sometimes we consider negatives of primes (-2, -3, -5, ...) as primes as well, but not usually.
Our entire system of arithmetic (addition and subtraction) rests on the prime numbers. In particular the theorem that every positive integer larger than one can be expressed as the product of a unique set of primes, eg 140 = 2 x 2 x 5 x 7, and there are no other primes which when multiplied together will give 140. An impeccable proof of this was given by the Greek mathematician Euclid.
If this (The Unique Prime Factorization Theorem) wasn't true, maths would be very different. The world would also be very different!
The biggest problem with primes is that we don't know how to find them. What would be nice would be a polynomial (a formula of the form f(x) = anxn + an-1xn-1 + ... + a1x + a0, eg x3 + 3x2 - 7) that gives us only prime numbers. No such polynomial exists. There are some other formulae that do give the nth prime, but they are far, far , FAR too cumbersome to be of any use. There are some polynomials that give several primes though, like this one (n2+n+41), given on page 435 of ``Rama II'', by Arthur C. Clarke and Gentry Lee:
O'Toole never fully comprehended what exactly was meant by the expression `quadratic prime'. However he did understand, and was fascinated by, the fact that the string 41, 43, 47, 53, 61, 71, 83, 97, ... , where each successive number was computed by increasing the difference from the previous number by 2, resulted in exactly forty consecutive prime numbers. The sequence ended only when the forty-first number in the string turned out to be a non-prime, namely 41 x 41 = 1681.
(By the way, it's very easy to show that no polynomial with a constant term apart from -1 or 1 can produce all primes. Have a go at it!)
We'll get back to this business of finding specific primes later. Let's now consider the general distribution of primes. Are they evenly distributed amongst the integers? No. Consider the first 5000 numbers. Divide them into blocks of 1000 each. In the first block, 1 to 1000, there are 168 primes, in the second there are 135, followed by 127, 120 and 119. While if you consider the last five blocks before ten million, you find 62, 58, 67, 64 and 53 primes. Clearly, the frequency of primes tends to decrease as you go higher and higher, though neither strictly nor quickly.
We can express this more mathematically. Let N(n) be the number of primes less than n. In 1792, Karl Gauss conjectured (ie proposed that something might be true, without actually proving it) that N(n) approaches n/(ln n) as n becomes larger and larger. This was only proved a hundred years later by Jacques Hadamard and Charles de la Vallee-Poussin after initial work by Pafnuty Chebyshev.
However, his proof used calculus. It was only in 1949 when a non-calculus proof was given, by Selberg and Paul Erdos (this is the same Erdos who died in September 1996). It means that the frequency of primes decreases as we deal with larger and larger numbers. Does this mean that the number of primes is finite? No. Let me show you Euclid's famous proof of the infinitude of primes.
The technique involved in this proof is called ``proof by contradiction''. The idea is very simple. Say we want to prove that statement S is true. What we do is that we assume that S is false, and then try to show that this leads to a false conclusion. This would mean that our original assumption was false, and S must be true.
In this example, we wish to show that there are an infinite number of primes. So let us suppose there are a finite number, namely p1, p2,... , pn. Any number is a product of these numbers, as there are no other primes. But consider the number p1p2p3...pn-1pn + 1. It is not divisible by any of the n primes previously mentioned, is it? No. So it certainly cannot be represented as a product of any of those primes. This is a contradiction, so we must accept that there are an infinite number of primes.
An extension of the above proof was given by Lejeune Dirichlet. For any pair of integers a and b, there are an infinite number of integers of the form ax + b (where x is an integer). So ,for example, there are an infinite number of primes of the form 2x + 1 (the odd numbers), 3x + 7, 3146117x + 245113, etc. But the proof is too complicated for this article.
The theory of primes is loaded with unsolved problems --- here's another. There are several known `twin primes', which are pairs of primes 2 apart, eg 5 & 7, 11 & 13, 29 & 31, etc. Are there an infinite number of prime pairs? Nobody knows. For those of you who like to show off to your friends by quoting mindless figures, the largest twin primes known are (242206083)(238880) - 1, and (242206083)(238880) + 1 which were discovered by two guys called Indlekofer and Ja'rai in November 1995. Each number has 11713 digits and would take up over two pages (pages? pages on a computer screen?) of this article if written out in full!
Now for some famous failures with primes. Pierre de Fermat conjectured that 22n+1 would produce a prime number for all positive integral values of n. Things seemed alright. The first four Fermat numbers, namely 5, 17, 257, 65537 were definitely prime. What of the rest? They were too large to deal with, but certainly looked prime. Then - wham! 50 years after Fermat had begun decomposing, Leonhard Euler showed that F5 was composite (not prime). His method is very interesting:
F5 = 232 + 1
= (16)228 + 1
= (641 - 54)28 + 1
= 641m - (5 x 27)4 + 1
= 641m - (641 - 1)4 + 1
= 641n - 1 + 1
= 641n
In case you were wondering, the m and n that suddenly appear in the proof represent integers whose actual value is unimportant. You know, it's sad that such elegant proofs are no longer feasible. All big primes for the last 50 years have been found using computers. Also sad is the fact that of all the other Fermat primes above F5 found so far, none are prime!
One question you probably want to ask is ``what is the largest known prime?'' The answer is 21257787-1, which has 378632 digits! This prime was discovered by accident earlier this year by David Slowinski and Paul Gage at Cray Research. There's something special about this number --- it's a Mersenne prime. Let me explain that.
Initially it was thought that all numbers of the form 2n-1 were prime, but this idea was squashed in 1536 when Hudalricus Regius showed that 211-1 = 2047 was not prime as it was the product of 23 and 89. Over a century later a French monk called Marin Mersenne stated that such numbers were prime for n = 2, 3, 5, 7, 13, 17, 19, 31, 127, 257 and were composite for all other values of n less than 257. He was wrong, but still got his name attached to these numbers, so we call 2n-1 the nth Mersenne number, or Mn. This was probably because it took 240 years for anyone to prove that he was wrong! Then, Pervouchine showed that M61 = 261 - 1 was prime. And it was only in 1947 that all of the first 257 Mersenne numbers were finally checked. We now know that Mersenne's list should have been n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127. Currently, at least the first 365000 Mersenne numbers have been analysed --- a few are prime, most are not. A major use of Mersenne numbers is in the search for the largest (un)known prime, for almost all of the largest known primes in history have been Mersenne primes.
Thus ends this article on prime numbers, but let me leave you with one last result, first proved by Euler. Consider the sum of all the reciprocals of primes, ie 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + 1/13 + ...One would expect this sum to exist, but it just doesn't! The series diverges, though extreeeeeemly slowly. Proofs of this are in several books, including my personal favourite ``An introduction to the theory of numbers'' by Hardy and Wright.
UPDATE: on 13 November 1996, Joel Armengaud was running a program written by George Woltman, when he stumbled across the prime 2^1398269 -1. This new prime is the 35th known Mersenne prime and is 420,921 digits long. The discovery was due to the Great Internet Prime Search which you can join for free! (They provide the software, you provide the hardware)
Other prime sites include