Problems with TIM MELROSE & PAUL SCOTT Introduction Nowadays it is boasted about by computer manufacturers or software companies to seek A prime number is an integer greater than 1 publicity. that is divisible by only itself and 1. Primes certainly would occupy a less For example the first ten primes are: central position in number theory were it not for a result known as the Fundamental 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. Theorem of Arithmetic which states: A positive integer greater than 1 that is not Any positive integer (other than 1) can be a prime is called composite. written uniquely as the product of prime The number 1 itself is considered neither numbers. prime nor composite. In fact Ernst Gabor Strauss (1922–1983) was said to have replied As the name suggests it is one of the most to a student’s question about why 1 is not a basic but important propositions in all of prime: mathematics. Primes, once associated exclusively with The primes are the building bricks for pure mathematics, have recently found an arithmetic, and 1 is just not a brick! unexpected application in the areas of national security, and in particular public-key One of the few things we know about cryptography. This uses the principle that it is primes is that there are infinitely many of very difficult to find the factors of a given them. This was proved by the ancient Greeks, product of two very large primes. and Euclid in particular, in about 350 B.C. The largest prime known today is Mersenne’s work 225964951–1 The French priest Marin Mersenne which was announced on 18 February 2005. (1588–1648) played an important role in 17th The discovery of a new prime used to be century number theory and also more general celebrated with a glass of wine or a postage mathematics. Scholars inquisitive about stamp: mathematics or stumped by a difficult problem would often write to Mersenne who could direct them to a likely authority, if he did not know the answer himself. Today Mersenne’s name is mainly associated with numbers of the form 2n – 1; that is, numbers one less than a power of 2. To honour Mersenne these are called Mersenne numbers. It is clear that all such numbers are odd but more importantly some of them are prime; as 2 amt 61 (3) is the case with 213466917 – 1. Mersenne immediately understood that if n is composite then 2n – 1 must also be composite. For example taking n = 33, then 233 – 1 = 8589934591 = 7 × 1227133513 is not a prime. However when n is prime, the situation becomes less clear. Letting p = 2, 3, 5, and 7 yields the “Mersenne primes” 22 – 1 = 3, 23 – 1 = 7, 25 – 1 = 31, and 27 – 1 = 127 respectively. But if we take p = 11 as the expo- nent we get 211– 1 = 2047 = 23 ×89. Mersenne Marin Mersenne Carl Friedrich Gauss (1588–1648) (1777–1855) was also fully aware that a prime p was not enough to guarantee 2p– 1 to also be prime. In fact he made the following assertion in his 193707721 × 761838257287 book Cognitata Physica-Mathematica: which he also computed silently. The product The only primes between 2 and 257 for which was none other than 2p – 1 is prime are p = 2, 3, 5, 7, 9, 11, 13, 17, 19, 31, 67, 127 and 257. 147573952588676412927. Unfortunately Mersenne missed the fact Cole then took his seat without uttering a that the numbers 261 – 1, 289 – 1 and 2107 – 1 word. Those in the audience, having just are in fact prime. But conversely 267 – 1 and witnessed the explicit factorisation of 2257 – 1 turned out not to be prime at all. We Mersenne’s number 267 – 1 into its two huge can forgive Mersenne for these errors as he factors, then burst into unanimous applause lived in the pre-computer age. The case of for Cole and gave him a standing ovation. 267–1 was proved by Edouard Lucas It was not until a while after the meeting (1842–1891) in 1876 who used an argument that Cole admitted he had been working on the which did not explicitly yield any of the calculation for the previous two decades! factors. It was not until the following century In spite of Cole’s factorisation, Mersenne that Frank Nelson Cole did find its factors. numbers remain a plentiful source of primes. In fact the five largest primes known today are Mersenne primes. For more information on the 267 – 1 is composite! current search for primes see www.utm.edu/research/primes/largest.html. In 1903 at a meeting of the American Mathematical Society, among the speakers on the agenda was Frank Nelson Cole. When it came Cole’s turn, he Gauss’s contribution purposefully walked to the front of the room and without saying anything, proceeded to multiply 2 by In his article 329 Disquisitiones Arithmeticae itself 67 times under his breath. He then subtracted (1801), the German mathematician Carl 1 and finally arrived at the enormous result of Friedrich Gauss (1777–1855) wrote: 147573952588676412927. The problem of distinguishing prime numbers from composite numbers and of Having witnessed this wordless calculation, resolving the latter into their prime factors is the bemused audience then watched as he known to be one of the most important and wrote on the blackboard useful in arithmetic. It has engaged the industry and wisdom of ancient and modern amt 61 (3) 3 geometers to such an extent that it would be Other facts about primes superfluous to discuss the problem at length… Further, the dignity of science itself The answer to the question of how many prime seems to require that every possible means numbers exist is given by the fundamental be explored for the solution of a problem so theorem: elegant and so celebrated. There exist infinitely many prime numbers. One of the most intriguing aspects of primes is that there is no obvious pattern Euclid was the first to prove this (c 350 BC). governing their distribution among the posi- His proof is also one of the simplest. tive integers. In fact all attempts to find a formula that will produce only primes, or even Euclid’s Proof. Suppose that predict their exact distribution, have so far p = 2 < p = 3 < … < p 1 2 r failed. But Gauss switched his attention from are all the primes. Let finding individual primes to finding their P = p p … p +1 1 2 r average distribution. and let p be a prime dividing P. Then p cannot In 1792, at the age of 15, Gauss examined be any of p , p , … p, otherwise pwould divide 1 2 r a table of prime numbers compiled by the the difference P – p p … p = 1, which is 1 2 r German-Swiss Mathematician Johann impossible. So this prime p is still another Heinrich Lambert (1728–1777). Gauss was prime, and p , p , … p would not be all the 1 2 r seeking a rule which governs the number of primes. primes less than or equal to some integer x. We denote this number by π(x). For example However the proof of Euclid’s theorem does since there are 6 primes smaller than 14, we not give us a way of producing new primes have π(14) = 6. A closer examination indicates since, for example, that on average the gaps between primes becomes larger and larger. Gauss asked 2 × 3 × … × 13 + 1 = 30031 = 59 × 509. whether for large x the behaviour of π(x) could be approximated by a known function. Gauss One of the ways to find all primes less than then made a bold conjecture which he scrib- or equal to N is to list all numbers less than or bled on the back of his table of logarithms. It equal to N and then cross out all multiples of read primes. Those numbers left must be primes. This method is called the Sieve of primzahlem unter a (= ∞) a/ln a. Eratosthenes, named after Eratosthenes (who lived in the third century BC), but is obviously This can be interpreted as saying not practical for larger numbers. For example if we take N = 100, and we cross off all multi- π(a) ~ a/ln a for large values of a. ples of primes, then the remaining numbers (in white, below) are all the primes. Gauss did not attempt to prove his conjec- ture, he merely got a sense of what he thought 1 2 3 4 5 6 7 8 9 10 the answer should be. The proof (of the more 11 12 13 14 15 16 17 18 19 20 precise result involving limits) eluded many great minds including Georg Friedrich 21 22 23 24 25 26 27 28 29 30 Bernhard Riemann (1826–1866), himself a 31 32 33 34 35 36 37 38 39 40 student of Gauss, who published a paper on 41 42 43 44 45 46 47 48 49 50 the subject in 1859. Success finally came in 51 52 53 54 55 56 57 58 59 60 1896 when Jacques Salomon Hadamard 61 62 63 64 65 66 67 68 69 70 (1865–1963) of France and Charles de la Vallée-Poussin (1866–1962) of Belgium inde- 71 72 73 74 75 76 77 78 79 80 pendently proved Gauss’s conjecture. Today 81 82 83 84 85 86 87 88 89 90 this result is known as The Prime Number 91 92 93 94 95 96 97 98 99 100 Theorem. 4 amt 61 (3) Some known results about 2. Every integer n greater primes than or equal to 5 is the sum of three primes. • In 1845 Bertrand (1822–1900) investigated experimentally the properties of π(x), the As far as is known, number of primes less than or equal to x. Euler did not prove (1), but As a result, he conjectured: neither Euler nor anyone else has been able to find a For n > 1, between n and 2n there is always counter-example. This a prime number. conjecture has since been tested for all even numbers This was proved by Tschebycheff in 1852. up to at least 1010 and found to be true. This still • In 1837, Dirichlet (1805–1859) proved that remains one of the great an arithmetic progression {a + nb}, where a unsolved conjectures of Pierre de Fermat (1601–1655) and b are relatively prime, contains an infi- mathematics. nite number of primes. Pierre de Fermat (1601–1655) conjectured that • There exist arbitrarily long stretches of numbers which do not contain a prime. For F = 22n + 1 n example 1000! +2, 1000! +3, … 1000! +1000 is prime for any non-negative integer n. The is a stretch of 999 consecutive composite conjecture was proven to be incorrect in 1732, numbers. when Euler showed that F5 = 4294967297 = 6700417 × 641. Unproved conjectures More recently analysis of these so-called Primes have a tendency to arrange themselves Fermat numbers have found no other primes in pairs of the form (p, p+2): for example 3 and above F . However no-one has yet proved that 4 5, 5 and 7, 17 and 19. This is also evident F is the largest Fermat prime. 4 among much larger numbers such as 29 879 and 29 881. Such primes are called twin primes or prime pairs, and it is not known References whether there are infinitely many of these twin primes. However most mathematicians believe Caldwell, C. (n.d.). The Primes Pages. Accessed at http://www.utm.edu/research/primes/largest.html. the answer is, “Yes”. Dunham, W. (1994). The Mathematical Universe. New York: John A more famous conjecture regarding primes Wiley & Sons. is the Goldbach Conjecture, named after Maor E. (1994). The Story of a Number. Princeton: Princeton University Press. Christian Goldbach (1690–1764), a German Mollin, R. A. (1998). Fundamental Number Theory with mathematician who later became Russia’s Applications. New York: CRC Press. foreign affair minister. In a letter to Euler Ribenboim, P. (1996). The New Book of Prime Number Records. New York: Springer-Verlag. (1742) he conjectured: Ribenboim. P. (2000). My Numbers, My Friends. New York: Springer-Verlag. 1. Every even number greater than or equal to 4 is the sum of two primes; for example 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7. Tim Melrose Wynn Vale, SA (It is easy to verify that this conjecture fails for [email protected] odd numbers, 11 for example.) In the letter Goldbach also expressed the Paul Scott Wattle Park, SA following belief: [email protected] amt 61 (3) 5