How primesfit into the number jigsaw

How can we be sure that the primes do not become 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 of primes(something explained more carefully in a moment), there must then be infinitely many primes to do the job. Although this conclusion is true, it does not follow from the previous observations, for if we begin with afinite collection of primes, there is no end to the number of different numbers we can produce just using those given prime factors.Indeed, there are infinitely many different powers of any single prime:for example, the powers of the prime 2 are2,4,8,16,32,64,···. It is conceivable therefore that there are onlyfinitely many primes and every number is a product of powers of those primes. What is more, we have no way of producing an unending series of different primes the way we can,for example, produce any number of squares, 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 of this chapter, butfirst 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 of a multiple of 6. In other words, any prime after these firsttwohastheform6n±1 for some number n.(Remember that6nis 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 of six. 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 if you 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 6nand 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±1canbe prime.Thecasewhereboth of the numbers 6n±1areprime corresponds exactly to the twin primes:for example(6×18)±1gives the pair 107,109 mentioned in thefirst 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 of primes up to 100 but thefirst failure is not far away:(6×20)-1=119=7×19, while(6×20)+1=121=112, so neither number is primewhenwetaken=20.

And the principal reason why primes are important is that every number can be written as a product of prime numbers, and that can be done in essentially only one way. Tofind this special factorization, we just 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 that120=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 the prime factorization of120is23×3×5. We could,however, have came to this by another route. For instance but rearranging the prime factors from least to greatest still yields the same result as before:120=23×3×5.

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

At least it did in that example, and this behaviour may be 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 samefinal 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 euclidean property:ifaprime 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 of 35. This property characterizes primes as no composite number can give you the same guarantee:for example,we see that 6 is a factor 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 argument based on what is known as the Euclidean Algorithm, which will be explained in Chapter 4. If we 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.

If these two factorizations of n had a prime p in common, we could cancel p from both and obtain two different prime factorizations of the smaller number np.Sincenis the smallest number with two distinct prime factorizations, this is not possible and so the sets of primes involved in each factorization of nmust have no prime in common. Now take one prime p that occurs in one of these factorizations of n. Since this prime p is a factor of n,it follows that p is a factor of the second factorization, and so, by the euclidean property, p is a factor of one of the primes, q say, of the second factorization. But since q and p are both prime,thisis only possible if q=p, a possibility that we have already discounted as the two factorizations of n have no common prime. And so we arrive at afinal contradiction, showing that it is impossible for such a number nto exist. Therefore we conclude that the prime factorization of every number is unique.

It is worth noting that the uniqueness of prime factorization would not hold if we included the number 1 among the primes, as we can adjoin any power of 1 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 of prime 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. If someone 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 of all. 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 conceivablefinite collection of primes, we can produce a new prime not in the list. For example, if someone claimed there was a largest odd number out there somewhere, you could refute him by saying that if nis 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 afinite list of primes, we have no way of using the collection to manufacture a prime that is demonstrably bigger than all of them. Perhaps there is a biggest prime after all?How are we to know that 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 notfind a way of generating a new prime, so he reverted to an argument that is one step more subtle. He showed that there must be one or more new primes within a certain range ofnumbers(but his argument does not allow us to locate exactly where tofind a prime within that range).

It goes like this. Let p1, p2,···, pk be the list of thefirst kprimes say, and consider the number nthat is one more than the product of all these primes, so that n=p1p2···pk+1.Eithernis a prime,or is divisible by a prime smaller than itself, which cannot be any of p1, p2,···, pk,asifp is any one of these primes, then dividing nby p will leave a remainder of 1. It follows that any prime divisor of nis 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 nofinite 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 tofind 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 infinitely 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=1andb=2, we get the sequence of odd numbers which we know, by Euclid’s proof, contains infinitely 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,and5+8n(as nruns through the successive values 1,2,3,···), each have infinitely many primes. The general result of Dirichlet is, however,very difficult to prove.

Another simply stated result is that there is always at least one prime number greater than any given number nbut less than 2n(for n≥2).(As an aid to memory, inequality signs such as this one, which stands for greater than or equal to, always point to the smaller quantity.)This fact, historically known as Bertrand’s Postulate, can be proved using quite elementary mathematics,although the proof is itself quite tricky. We can verify the postulate for n up to 4000 by making use of the following list of primes.First observe that each number in the list after the initial prime 2is smaller than twice its predecessor:

2,3,5,7,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＜2nand 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 coefficients(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 far before meeting similar-sounding problems that as yet remain unsolved. For example, no one knows if there is always a prime between any two consecutive squares. Another observation is that there seems to be enough primes to ensure that every even number ngreater than 2is the sum of two of them(Goldbach’s Conjecture). This has been directly verified for nup 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=2n for 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 off.

A simple result that has something of theflavour 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 nin order to know that it must exist. Sometimes it is possible to know for certain that there are solutions to a problem, without actuallyfinding any of those solutions explicitly.

In this case, we begin by noting that if we 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,fromwhich 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/lognand that the approximation becomes more and more accurate as n increases. For example, if we take nto be one million,the ratio of n/lognsuggests 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 naturallogarithm, 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 only be 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 as polynomials,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=0ton=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 forn=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 if we 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 called factorials, which we will meet again in Chapter 5.The number n!, read‘n factorial’, is just the product of all numbers up to n.Forexample,5!=5×4×3×2=120. Wilson’s Theorem is then a very succinct statement:a number p is prime if and only if p is a factor of 1+(p-1)!.

The proof of this result is not very difficult, and indeed in one direction it is nearly obvious:if p 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,wewillobtaina remainder of 1.(The case where a=b requires a little more thought.)This is very reminiscent of Euclid’s proof for the infinity of primes. It follows that if p is a factor of 1+(p-1)!then p must be prime. The converse is a little harder to prove:if p is prime then p is a factor of 1+(p-1)!. This, however, is the surprising direction of the theorem, although the reader can easily verify particular cases:for example, the prime 5 is indeed a factor of

1+4!=1+24=25.

As afinal observation, we can exploit factorials, which by design have many factors, in order to prove that no arithmeticsequence of numbers, that is to say one of the form a,a+b,a+2b,a+3b,···can consist only of primes 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 isfixed at b. To see this,consider the sequence of nconsecutive integers:

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

Each of these numbers is composite, as thefirst 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 thefinal one in the list, which has n+1 as a factor. We therefore have, for any given n, a sequence of n consecutive numbers, none of which are prime.

Instead of focusing 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.