How primes fit into the numberjigsaw

How can we be sure that the primes do notbecome rarer and rarer and eventually peter out altogether? You might think that since there are infinitely many counting numbers and each can be broken down into a product ofprimes(something explained more carefully in a moment), there must then be infinitely many primes to do thejob. Although this conclusion is true, it does not follow from the previous observations, for ifwe begin with a finite collection of primes, there is no end to the number ofdifferent numbers we can producejust using those given prime factors.Indeed, there are infinitely many different powers ofany single prime:for example, the powers of the prime 2 are2,4,8,16,32,64,…. It is conceivable therefore that there are only finitely many primes and every number is a product of powers ofthose primes. What is more, we have no way of producing an unending series ofdifferent primes the waywe can,for example, produce any number ofsquares, or multiples of a specific given number. When it comes to primes, we still have to go out hunting for them, so how can we be sure they do not become extinct?

We will all be sure by the end ofthis chapter, but first I will draw your attention to one simple‘pattern’among the primes worth noting. Every prime number, apart from 2 and 3, lies one side or the other ofa multiple of 6. In other words, any prime after these first two has the form 6n±1 for some number n.(Remember that6n is short for 6×n and the double symbol±means plus or minus.)The reason for this is readily explained. Every number can be written in exactly one of the six forms 6n,6n±1,6n±2, or6n+3 as no number is more than three places away from some multiple ofsix. For example,17=(6×3)-1,28=(6×5)-2,57=(6×9)+3;indeed, the six given forms appear in cyclic order,meaning that ifyou write down any six consecutive numbers, each of the forms will appear exactly once, after which they will reappear again and again, in the same order. It is evident that numbers of the forms 6n and 6n±2 are even, while any number of the form 6n+3 is divisible by 3. Therefore, with the obvious exceptions of 2 and 3, only numbers of the form 6n±1 can be prime. The case where both of the numbers 6n±1 are prime corresponds exactly to the twin primes:for example(6×18)±1gives the pair 107,109 mentioned in the first chapter. You might be tempted to conjecture that at least one of the two numbers6n±1 is always prime–this is certainly true for the list ofprimes up to 100 but the first failure is not far away:(6×20)-1=119=7×19, while(6×20)+1=121=112, so neither number is prime when we take n=20.

And the principal reason why primes are important is that every number can be written as a product ofprime numbers, and that can be done in essentially only one way. To find this special factorization, wejust need to factorize the given number in some way and then continue factorizing any composite factors that appear until this can be done no more. For example, we could say that 120=2×60 and continue by breaking the composite factor of 60 down further to give:

120=2×60=2×(2×30)=2×2×(2×15)=2×2×2×3×5.

We say that theprimefactorization of 120 is 23×3×5. We could,however, have came to this by another route. For instance

120=12×10=(3×4)×(2×5)=(3×(2×2))×(2×5)

but rearranging the prime factors from least to greatest still yields the same result as before:120=23×3×5.

At least it did in that example, and this behaviour maybe more or less familiar to you, but how can you be sure that this applies to every number? It is clear enough that any number can be broken down into a product of primes but, since there is in general more than one way of tackling this task, how can we be sure that the process will always deliver the same final result? This is an important question, so I will take a few moments to give an outline of the reasoning that allows us to be absolutely sure about this. It is a consequence of another special property of prime numbers that we shall call the euclideanproperty:ifa prime number is a factor of a product of two or more numbers, then it is a factor of one of the numbers in that product. For example,7 is a factor of 8×35=280(as the product 280=7×40)and we note that 7 is a factor of35. This property characterizes primes as no composite number can give you the same guarantee:for example,we seethat 6 is afactor of 8×15=120(as 120=6×20)yet 6 is not a factor of either 8 or 15.

The fact that primes always have the above property can be proved using an argumentbased on what is known as the Euclidean Algorithm, which will be explained in Chapter 4. Ifwe take this on trust for the time being, it is not too difficult to explain why no number could have two different prime factorizations, for suppose there were such a number. There then would be a smallest one that behaved in this way:let us denote it by n and so nhas two prime factorizations which, when the prime factors are written in ascending order, are not identical. We shall show that this leads to contradiction and so must be false.

It is worth noting that the uniqueness ofprime factorization would not hold ifwe included the number 1 amongthe primes, as we can adjoin any power of1 to a factorization and the product retains the same value. This shows that 1 is fundamentally different in nature to the primes, and so it is right to frame the definition ofprime number in a way that excludes 1 from the collection.

Euclid's infinity of primes

Let us return to the question as to how we know that the primes go on forever and that there is no way past them. Ifsomeone claimed that 101 is the largest prime, you can refute him at once by showing that 103 has no factors(except for 1 and 103)and so 103is a larger prime. Your friend might then concede that he made a slip and that he should have said that it was 103 that is the largest prime ofall. You could then show him up again by demonstrating that 107 is also prime, but your friend might still persist in his error by adjusting his position to the largest prime number on view. He could even retreat a little further and admit that he does not know the identity of the largest prime but nevertheless continue to claim that he is certain that there is one.

The best way to settle this question would be to show that, given any conceivable finite collection of primes, we can produce a new prime not in the list. For example, ifsomeone claimed there was a largest odd number out there somewhere, you could refute him by saying that ifnis odd, then n+2 is a larger odd number, so there cannot be a largest odd number. This approach, however, is not so easy for the primes–given a finite list of primes, we have no way of using the collection to manufacture a prime that is demonstrablybigger than all of them. Perhaps there is a biggest prime after all? How are we to knowthat our stubborn friend isn’t right?

Euclid of Alexandria(c.300 BC), the Greek mathematician and father of all things euclidean, did however know. Given a list p1, p2,…, pk where each of the pi denotes a different prime, he could not find a way of generating a new prime, so he reverted to an argument that is one step more subtle. He showed that there mustbe one or more newprimes within a certain range of numbers(but his argument does not allow us to locate exactly where to find a prime within that range).

It goes like this. Let p1, p2,…, pk be the list of the first kprimes say, and consider the number nthat is one more than the product of all these primes, so that n=p1p2…pk+1. Either n is a prime,or is divisible by a prime smaller than itself, which cannot be any of p1, p2,…, pk, as ifp is any one of　these primes, then dividing nby p will leave a remainder of 1. It follows that any prime divisor of n is a new prime that is greater that all the primes p1, p2,…, pkand no more than nitself. In particular, it follows from this that there can be no finite list of primes that contains every prime number, and so the sequence of primes continues on forever and will never be exhausted. Euclid’s eternal proof of the infinity of primes is among the most admired in all of mathematics.

Although Euclid’s argument does not tell exactly where to find the next prime number, the overall frequency of the primes is now quite well understood. For example, if we take any two numbers,a and b say, with no common factor and consider the sequence a,a+b,a+2b,a+3b.., it was shown by the German mathematician Johann Dirichlet(1805–59)that innitely many members of such a sequence are prime.(Of course, there is no hope if a and b do have a common factor, d say, as then every member in the list is also a multiple of d, and so is not prime.)When a=1 and b=2, we get the sequence of odd numbers which we know, by Euclid’s proof, contains innitely many prime numbers. Indeed, it can be shown through fairly simple adaptations of Euclid’s argument that other special cases such as the sequence of numbers of the forms 3+4n,5+6n, and 5+8n(as n runs through the successive values 1,2,3,...), each have innitely many primes. The general result of Dirichlet is, however,very difcult to prove.

2,3,57,13,23,43,83,163,317,631,1259,2503,4001.

For each n in the range up to 4000, take the largest prime p in the list that is no more than n;the next prime q then lies in the range n＜q＜2n and this then ensures that Bertrand’s Postulate holds for all n up to 4000. For example, for n=100, p=83, and then q=163＜2×100. A subtle argument involving the size of the so-called central binomial coefcients(introduced in Chapter 5)then shows that the postulate is also true for n larger than 4000.However, we do not have to go too farbefore meeting similar-sounding problems that as yet remain unsolved. For example, no one knows ifthere is always a prime between anytwo consecutive squares. Another observation is that there seems to be enough primes to ensure that every even number n greater than 2is the sum of two of them(Goldbach’s Conjecture). This has been directlyverified for n up to 1018. We might then hope for a proof along the lines above for Bertrand’s Postulate, where we show that beyond a certain specified integer N, we may introduce a comparison based on what is known about the distribution of　the primes to ensure that there will always be at least one solution in primes p, q to the equation p+q=2nfor any even number2n≥N. This still eludes us, although there are weaker results along these lines–for example, it has been known since 1939 that every sufficiently large odd number is the sum of　at most three prime numbers and that every even number is the sum of　no more than 300,000 primes. Proof of the full Goldbach Conjecture still seems a long way of f.

A simple result that has something of the flavour of the argument type referred to above is that there is a number nless than 4 billion that can be written as the sum of　four different cubes in ten distinct ways. It is known that 1729=13+123=93+103 is the smallest number that is the sum of　two cubes in two different ways. However, we do not necessarily have to identify the number n in order to know that it must exist. Sometimes it is possible to know for certain that there are solutions to a problem, without actually finding any of　those solutions explicitly.

In this case, we begin by noting that ifwe take four different numbers no more than afixed integer mand form the sum of　their cubes, the result is less than 4m3. However, ifm=1000, then an elementary calculation shows that the number of　sums of　four different cubes is more than 10 times the number 4m3, from which it follows that some number n≤4m3=4,000,000,000 must be the sum of　four cubes in at least ten different ways. The details involve calculations using binomial coefficients(introduced in Chapter 5)and are not especially difficult.

The global picture of prime distribution is summed up by the observation of the leading 19th-century German mathematician and physicist Karl Friedrich Gauss(1777–1855)that p(n), the number of primes up to the number n, is approximately given by n/logn and that the approximation becomes more and more accurate as n increases. For example, ifwe take nto be one million,the ratio of n/logn suggests that, up to that stage, about one number in every 12.7 should be prime. Gauss’s observation, which in detail says something more precise, was not proved until 1896.The logarithm function referred to here is the so-called natural logarithm, which is not based on powers of 10, but rather on powers of a special number e, which is approximately equal to2.718. We shall hear more of this very famous number e in Chapter 6.

The most celebrated undecided question in number theory is the Riemann Hypothesis, which can onlybe explained in terms of complex numbers, which we have yet to introduce. However,I mention it here as the object of the question can be reformulated using the uniqueness of prime factorization to involve a certain infinite product featuring all the primes. This leads to an interpretation which says that the Hypothesis implies that the overall distribution of the primes is very regular in that, in the long run, primality will apparently occur randomly. Of course, whether or not a particular number is a prime is not a random event but what is meant is that primality, in the realm of the very large, takes on the mantle of randomness, with no additional pattern or structure to emerge. Many a number theorist has a heartfelt wish to see this 150-year-old conjecture settled in their own lifetime.

Since they represent so natural a sequence, it is almost irresistible to search for patterns among the primes. There are, however, no genuinely useful formulas for prime numbers. That is to say, there is no known rule that allows you to generate all prime numbers or even to calculate a sequence that consists entirely of different primes. There are some neat formulas but they are of little practical worth, some of them even require knowledge of the prime sequence to calculate their value so that they are essentially a cheat. Expressions such as n2+n+41 are known aspolynomials,and this one is a particularly rich source of primes. For example,putting n=1,7, and 20 in turn yields the primes 43,107, and 461respectively. Indeed, the output of this expression is prime for all values of nfrom n=0 to n=39. At the same time, however, it is clear that this polynomial will let us down when we put n=41, as the result will have 41 as a factor, and indeed it fails for n=40as

402+40+41=40(40+1)+41=40×41+41=(40+1)41=412.

In general, it is quite straightforward to show that no polynomial of this kind can yield a formula for primes, even ifwe allow powers higher than 2 to enter the expression.

It is possible to devise tests for primality of a number that can be stated in a few words. However, to be of use they would need to be quicker, at least in some cases, than the direct verification procedure described in Chapter 1. A famous result goes by the name of Wilson’s Theorem. Its statement involves the use of numbers calledfactorials, which we will meet again in Chapter 5.The number n!, read‘nfactorial’, is just the product of all numbers up to n. For example,5!=5×4×3×2=120. Wilson’s Theorem is then a very succinct statement:a number p is prime ifand only ifp is afactor of 1+(p-1)!.

The proof of this result is not very difficult, and indeed in one direction it is nearly obvious:ifp were composite, so that p=ab say, then since both a and b are less than p, they each occur as factors of (p-1)!and so p is a divisor of this factorial as well. It follows that when we divide 1+(p-1)!by p, we will obtain a remainder of 1.(The case where a=b requires a little more thought.)This is very reminiscent of Euclid’s prooffor the infinity ofprimes. It follows that ifp is a factor of1+(p-1)!thenp must be prime. The converse is a little harder to prove:ifp is prime then p is a factor of 1+(p-1)!. This, however, is the surprising direction of the theorem, although the reader can easilyverify particular cases:for example, the prime 5 is indeed a factor of1+4!=1+24=25.

As afinal observation, we can exploit factorials, which by design have many factors, in order to prove that no arithmetic sequence ofnumbers, that is to say one of the form a, a+b, a+2b, a+3b,…can consist only ofprimes as it is possible to show that the gap between successive primes can be arbitrarily large while the common difference between consecutive members of the previous sequence is fixed at b. To see this,consider the sequence ofn consecutive integers:

(n+1)!+2,(n+1)!+3,(n+1)!+4,…,(n+1)!+n+1.

Each of these numbers is composite, as the first is divisible by 2(as each of the terms has 2 as a factor), the second is divisible by 3, the next by 4, and so on up until the final one in the list, which has n+1 as a factor. We therefore have, for any given n, a sequence ofn consecutive numbers, none ofwhich are prime.

Instead offocusing on numbers with the fewest possible factors(the primes), we shall in the next chapter turn to numbers with many factors, although we shall discover that here too there are surprising links to some very special prime numbers.