SEARCHING FOR PRIMES - Special Numbers - Numbers: Their Tales, Types, and Treasures

Numbers: Their Tales, Types, and Treasures.

Chapter 8: Special Numbers

8.2.SEARCHING FOR PRIMES

Mathematicians have spent years trying to find a general formula that would generate primes. There have been many attempts, but none have succeeded. We can test the expression n2n + 41 as a possible formula for generating prime numbers by substituting various positive values for n.As we proceed, we begin to notice that as n ranges in value from 1 through 40, only prime numbers are being produced. When we let n = 41, the value of n2n + 41 is (41)2 – 41 + 41 = (41)2, which is not a prime number. A similar expression, n2 – 79n + 1601, produces primes for all values of n up to 80. But for n = 81, we have (81)2 – 79 × 81 + 1601 = 1763 = 41 × 43, which is, again, not a prime number. You might now wonder if it is possible to have a polynomial expression in n with integral coefficients whose values would be primes for every positive integer n. Don't waste your time, since the Swiss mathematician Leonhard Euler (1707–1783) proved that no such formula can exist. Euler showed that any proposed expression will produce at least one nonprime. The idea of Euler's proof is rather simple. It goes this way: First assume that such a polynomial expression exists, and we represent it in general form as a + bx + cx2 + dx3 +…(understanding that some of the coefficients may be zero). Let the value of this expression be a prime number s when x = m (a positive integer). Therefore, s = a + bm + cm2 + dm3 +…. Similarly, let t be the value of the expression when x = m + ns, then

t = a + b (m + ns) + c (m + ns)2 + d (m + ns)3….

This may be transformed to

t = (a + bm + cm2 + dm3 +…) + A,

where A represents the remaining terms, all of which are multiples of s. (Moreover, it can be shown that A ≠ 0 for a suitable choice of n.) But the expression within the parentheses is, by hypothesis, equal to s. This makes the whole expression a multiple of s, that is, t = ks (with k > 1) and the number produced is, therefore, not a prime. Every such expression will produce at least one prime, but not necessarily more than one. Consequently, no polynomial expression can generate primes exclusively. Mathematicians continued to conjecture about forms of numbers that generated only primes, despite the fact that the above argument had already been accepted.

The French mathematician Pierre de Fermat (1601–1665), who made many significant contributions to the study of number theory, conjectured that all numbers of the form Fn = 2(2n) = 1, where n = 0, 1, 2, 3, 4…, were prime numbers. If you try this for Fn for values of n = 0, 1, 2, you will see that the first three numbers derived from this expression are 3, 5, and 17. For n = 3, you will find that Fn = 257, and F4 = 65,537. We notice these numbers are increasing in size at a very rapid rate. For n = 5, Fn = 4,294,967,297, and Fermat could not find any factor of this number. Encouraged by his results, he expressed the opinion that all numbers of this form are probably also prime. Unfortunately, he stopped too soon, for in 1732, Euler showed that F5 = 4,294,967,297 = 641 × 6,700,417, and it is, therefore, not a prime! It was not until 150 years later that the factors of F6 were found:

F6 = 18,446,744,073,709,551,617 = 247,177 × 67,280,421,310,721.

Many more numbers of this form have been found, but, as far as it is now known, none of them are prime numbers. It seems that Fermat's conjecture has been completely turned around, and one now wonders if any primes beyond F4 exist.

The largest known prime as of early 2013 is 257,885,161 – 1, which has 17,425,170 digits. This prime number is of the form 2k – 1, with some natural number k. Such primes are called Mersenne primes, as they were discovered by the French monk Marin Mersenne (1588–1648). The first few such Mersenne primes are obtained for k = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, and 127.

You may have noticed that all the numbers k in this list are prime numbers themselves. Indeed, 2k – 1 can only be prime when k is prime. But this does not guarantee that when k is prime, 2k – 1 will also be prime. For example, k = 11 is prime, but 211 – 1 = 2,047 = 23 × 89 is not a prime, and so k = 11 does not qualify.

While, according to Euclid's proof, there are infinitely many prime numbers, it is not known whether there are infinitely many Mersenne primes.

There are many interesting relationships regarding prime numbers. For example, the famous Goldbach conjecture made in a letter in 1742 to Leonhard Euler by German mathematician Christian Goldbach (1690–1764), which states that

· every even integer greater than 2 can be expressed as the sum of 2 prime numbers.

The first few of these are: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 7 + 7, 16 = 5 + 11, and so on. Remember, this is a conjecture, which implies that we have not yet proved that is true for all numbers; however, to date no one has ever proved it to be wrong. This is one of the ongoing challenges for number theorists.

There is also the twin-prime conjecture that states that there are infinitely many pairs of prime numbers whose difference is 2, such as the numbers 3 and 5, or the numbers 5 and 7, or the numbers 17 and 19 (adjacent encircled numbers in figure 8.2).

We also have a relationship among “three-primes,” where the difference between any two consecutive members of the triple is not greater than 4. For example, the simplest triple of such primes is (2, 3, 5). Another one would be (2, 3, 7). Table 8.1 lists a sampling of these prime triples.

2, 3, 5
3, 5, 7
5, 7, 11
7, 11, 13
11, 13, 17
13, 17, 19
17, 19, 23
37, 41, 43
41, 43, 47
67, 71, 73
97, 101, 103
101, 103, 107
103, 107, 109

107, 109, 113
191, 193, 197
193, 197, 199
223, 227, 229
227, 229, 233
277, 281, 283
307, 311, 313

7,873; 7,877; 7,879
247,603; 247,607; 247,609
5,037,913; 5,037,917; 5,037,919
88,011,613; 88,011,617; 88,011,619
1,385,338,061; 1,385,338,063; 1,385,338,067

Table 8.1: Some triples of primes.