 Teacher resources and professional development across the curriculum

Teacher professional development and classroom resources across the curriculum  # 1.5 Questions about Primes

## AN INFINITUDE OF PRIMES

• Euclid proved that, given a finite list of primes, one can always create a new prime not on that list, which implies that there are an infinite number of primes.

Let's take a look at a partial list of primes, with spaces left to represent the composite numbers that occur between them:

_2 3 _ 5 _ 7 _ _ _ 11 _ 13 _ _ _ 17 _ 19 _ _ _ 23 _ _ _ _ _ 29 _ 31 _ _ _ _ _ 37 _ _ _41 _ 43 _ _ _ 47 _ _ _ _ _ 53…

The primes seem to be haphazardly distributed; that is, there is not a clear pattern to them. It seems also, with the exception of the occasional pair of "twin primes"—primes separated by only one number—that the gaps between adjacent primes generally tend to become larger as the numbers themselves get larger. From this evidence, one could plausibly think that at some point the stream of primes dries up and that there might be no primes above some given number. The question of how many primes there are is an interesting one that arises quite naturally. Is the list finite or infinite?

Euclid thought about this problem and found a way to show that, in fact, there are an infinite number of primes to be found. He did this by demonstrating that from any finite collection of primes it is always possible to find one more. For example, take the finite set {2, 3, 5}. Euclid suggested multiplying all members of the set together and adding one. For our set, this gives us 31 (2 × 3 × 5 + 1 = 31), which cannot be evenly divided by any of the primes on our list, for it always gives a remainder of one. Hence, 31 is a "new" prime.

Remember that in math it's good to keep a skeptical, questioning attitude concerning pronouncements. Perhaps that example was just an anomaly, and maybe 2, 3, 5, and 31 are the only primes that exist. Applying Euclid's test strategy to this expanded set, we would multiply them together and get 930, to which we add one to end up with 931. Dividing 931 by 2, 3, 5, or 31 always leaves a remainder of one. Does this mean that 931 is prime? No, not necessarily, but it does mean that none of the numbers 2, 3, 5, and 31 is a factor of 931. It might not be obvious, but 931 is actually the product of 7, 7, and 19. So, even though 931 is not itself prime, it is a composite number whose prime factorization reveals new prime numbers (7 and 19) not in our original list. Again, our list was incomplete.

The point is that Euclid showed that multiplying together a finite list of primes and adding one will always produce a new number which, if not itself prime, factors into new primes not on the list. We can always find a new prime using this method. This implies that any finite list will never include all of the prime numbers; therefore, the list of primes must be infinite!

The method we employed above will always uncover at least one new prime, but it could very well miss some along the way. In our first example above, we missed a few primes in between 5 and 31, namely 11, 13, 17, 23, and 29. This method obviously will not produce an exhaustive list of primes; it serves only to generate a new prime or two, given a list of starting primes.

In the second example above, we found that this method produces a number that may not necessarily be prime. This suggests to us that it would be nice to have an efficient, fail-safe method for determining whether a number of any size is prime or not.

## IS IT PRIME?

• Determining whether or not a number is prime is a non-trivial task.

The most straightforward way to know for sure whether or not a number is prime is to test, systematically, its divisibility by all the numbers less than its square root. For example, if 1001 were composite, then it would have to be the product of two numbers, a and b, neither of which is one. One of these two numbers would have to be smaller than —they can't both be larger—so we need only check for divisors up to 32, which is the square root of the closest square number larger than 1001 (i.e., 1024). Because every number is composed essentially of prime factors, we need only check the prime numbers less than 32; these are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31. This is a feasible number of potential divisors to check.

There are a number of familiar divisibility tests that can be used to determine if a number is divisible by most of the single digit numbers. One rule that is widely known concerns divisibility by 3: a number is a multiple of 3 if all of its digits sum to a multiple of 3. For example, the digits of 78 sum to 15, and 78 factors to 3 × 26. What about a number such as 221, which doesn't fall in line with any of the short-cut divisibility tests? To determine whether or not it is prime, using the brute force method described above, we would have to divide it by all of the primes less than its square root, which is somewhere between 14 and 15. Were we to do this, we would find that our first five tries (checking 2, 3, 5, 7, and 11) would be unsuccessful, all yielding remainders. Only on the sixth try (dividing by 13) would we find that 221 is indeed factorable into 13 × 17.

The brute force method of testing whether or not a number is prime can prove to be quite a headache for large numbers. For example, using a computer that can perform tens of billions of operations per second, the test for a 100-digit number would take about 1040 seconds. This is quite a bit longer than the current estimated age of the universe, about 12 billion years.

There are various tests, other than the brute force method, that can tell us about the primeness of larger numbers. One such test uses Wilson's theorem, which states that if a number, p, is prime, then (p-1)! + 1 is a multiple of p. For example, we know that the number 7 is prime. Then, according to Wilson's theorem, (7-1)! + 1 = 6! + 1 = 721 should be a multiple of 7. Indeed it is: 721 = 7 × 103. Unfortunately, as we will see in Combinatorics Counts, computing factorials is practically infeasible for large numbers—e.g., 1000! is a number 2,568 digits long, and 1,000,000! is 5.5 million digits long. Wilson's theorem is useless for the sizes of numbers about which the question of primeness has not already been settled.

## THE STRUCTURE OF THE PRIMES

• The answer to whether or not there is a pattern behind the primes has eluded mathematicians for millennia.
• One can find interesting examples of both structure and randomness in the primes.

Because directly testing whether or not an arbitrary large number is prime is either very time-consuming or not very reliable, mathematicians have sought to determine the primeness of a number in a totally different way—that is, by looking for a pattern to the primes. If a pattern can be established, then it should be possible to determine where primes do and do not occur. Describing
exactly where primes should occur on the number line would not only provide an elegant way to know whether or not a number is prime—it would be a beautiful result in itself.

The first person generally credited with attempting to describe a pattern behind the primes was the Greek philosopher and mathematician Eratosthenes. He is credited with creating a method, now called the Sieve of Eratosthenes, for systematically identifying all prime numbers. His method is simple: begin with a finite list of whole numbers and eliminate all the multiples of 2 greater than 2, then all the multiples of 3 greater than 3, then all the multiples of 5 greater than 5, and so on until the only numbers left are the ones that are not multiples of any other numbers: these will be the primes. This method, however, is not terribly different or better for larger numbers than the brute force method we discussed earlier. It does, however, provide some possible clues to the structure of the primes available to us if, rather than looking at each number individually, we look at the structure as a whole. For example, can we find a pattern behind the primes by focusing on the spacing between them? This strategy is similar to looking at the negative space around a picture instead of looking directly at the picture itself. A Cup or two faces?

We can think of the space between primes as "prime deserts," strings of consecutive numbers, none of which are prime. There is a trick, however, for finding prime deserts of whatever length we can think of. For example, 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5,040. This number is, of course, not prime—but neither is 5,040 + 2, nor 5,040 + 3, nor 5,040 + 4. … nor 5,040 + 7. In general, for any number N, the string N! + 2, N! + 3,…N! + N identifies a string of N-1 consecutive composite numbers. Setting N = 1,000,000 shows that it is possible to find 999,999 consecutive whole numbers, none of which are prime.

Paradoxically, just as we can find prime deserts of whatever length we choose, we can also find strings of primes—sequences of primes that are evenly spaced on the number line—of whatever length we choose. A good example of strings of primes are the sets called "twin primes." These are pairs of primes that are spaced two numbers apart, such as 11 and 13, or 17 and 19. The set of 3, 5, and 7 forms another such string; again, each number is equally spaced from the others. In yet another example, the numbers 5, 17, 29, 41, and 53 are all prime and are all spaced evenly at 12 numbers apart. Such strings are called arithmetic progressions. In recently completed research done by Terence Tao at UCLA and Ben Green at the University of Bristol, arithmetic progressions of any finite length were proven to exist. Not only are there prime deserts of arbitrary length, but there are also strings of equally spaced primes of whatever finite length we choose. If there is a pattern to the primes, it would have to account for these paradoxically bizarre features.

A tantalizing clue as to the fundamental structure of the primes was discovered by Marin Mersenne, a French music theoretician and mathematician of the 16th and 17th centuries. Specifically, in his study of number theory he became interested in the powers of 2 and found an odd coincidence. Notice that, in the above chart, one less than a prime power of 2 yields a prime number. This seems to give us a potential way to predict where prime numbers fall, and it also shows a startling relationship. If the zero power is disregarded, these so-called Mersenne primes appear in the 2nd, 3rd, 5th, 7th , etc. positions in the sequence—in other words, in the prime positions. They are prime numbers in prime positions! Alas, this is but a coincidental occurrence in the smaller numbers, as the pattern does not hold for all prime powers of 2. For example 211 – 1 is equal to 2,047, which is the product of 89 and 23.

Mersenne primes, nonetheless, are still very important in the modern study of numbers. In fact, the largest prime number that we know about is a Mersenne prime. As of 2006, this number was 232582657 − 1, a number that is 9,808,358 digits long. It would take an average person more than 100 days just to read it! We should note that in addition to generating non-prime numbers, Mersenne's method also is not guaranteed to predict the positions of all of the primes.

We have so far looked at a few different approaches to predicting where primes should be found on the number line. From the brute force method of Eratosthenes to the elegant ideas of Tao, Green, and Mersenne, we have seen that the primes do not give up their secrets easily. Perhaps, in asking where exactly each prime falls on the number line, we are asking the wrong question. Gauss, of fundamental theorem of arithmetic fame, took a different approach. Finding a straightforward attack daunting, he examined matters from a different perspective. He examined the density of primes below a certain number. He found that the density of primes—that is, a measure of the number of primes in relation to all the numbers below any given number—is fairly constant. By looking at tables of the number of primes below a given number, n, Gauss observed that this measure always seems to be approximately the ratio , which implies that the nth prime is approximately n log n. This finding, while not exactly what we were looking for in terms of predicting where primes appear on the number line, represents a significant result in the search for a "law of the primes."

## RIEMANN'S HYPOTHESIS

• Riemann, following in the footsteps of Euler, thought that the pattern of the primes was tied to the zeta function, which is a generalization of the harmonic series.

Gauss's conjecture about the distribution of the primes was an important first step. By looking at the problem from a different perspective, that of prime density, and by examining functions that would give not a prime number directly, but rather the density of primes below a specified number, Gauss opened the exploration of the primes to new disciplines of mathematics. He was not the only one working on this problem, however. The Swiss mathematician Leonhard Euler, working in a similar vein, introduced yet another approach to discovering a pattern behind the primes.

Euler was fascinated by a relative of the harmonic series known as the zeta function. The harmonic series is simply the sum of the reciprocals of all the whole numbers. What tipped Euler off that the harmonic series' cousin, the zeta function, might be useful in exploring the structure of the primes was that it contains every natural number. Notice that the zeta function expresses the sum of the reciprocals of the xth power of every number. We can input any value we choose for x and study the behavior of the series. For any value of x less than or equal to one, the series diverges—grows infinitely large. For values of x greater than one, the series converges to a finite value. However, just because we know that the series converges does not mean that we can always find the value upon which it settles.

Euler played with the zeta function and found that he was able to express every element of the infinite sum as a product of the reciprocals of prime numbers. This insight tied the study of prime numbers to the study of infinite series and paved the way for one of the most elusive hypotheses in mathematics. Euler's Factorization Bernhard Riemann, one of the most influential mathematicians of the 19th century, built upon Euler's discovery, specifically exploring the consequences of using complex, or imaginary, numbers as the inputs to Euler's version of the zeta function. This effectively constructed a larger landscape of numbers to explore, one that gave a better perspective on how the elusive primes might be distributed along the number line. Riemann proposed that the distribution of the primes was tied to the zeroes of the zeta function when considered over the complex numbers.

If you imagine the entire collection of complex numbers to be a landscape with hills and valleys, the zeta function is like a road that traverses it. We can think of the zeroes of the zeta function as being the points at which the elevation of the road is at sea level. Riemann said that these points mark where the primes should occur.

Riemann's hypothesis was groundbreaking, but it remains a hypothesis, unproven, to this day. Given the history of the problem it purportedly solves, and the centuries of effort that have led to it, the proof of Riemann's hypothesis will be quite valuable. As of this writing, there is a \$1,000,000 reward available to any person who shows definitively whether or not it is true or untrue.

The preceding discussion should have given you a sense that primes are intrinsically fascinating. They are the fundamental basis of arithmetic—yet, they are extremely mysterious. They surprisingly represent both the most basic and the most cutting-edge aspects of mathematics. On a daily basis, however, we are not typically conscious of them. Because of this, it is tempting to believe that playing with primes is the purview of pure mathematics, with little relevance to our daily lives. This couldn't be further from the truth, especially in our modern age when numbers are used to transmit all types of information, the security of which is of great importance. Primes provide the building blocks of encryption schemes that protect our most sensitive and valuable data.