Related Links (Outside this Site)

---

(2006-11-25)   Prime Integers
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 ... (A000040)

A positive integer  p  is said to be  prime  when it has just two divisors among positive integers  (1 and p).

Besides the number 1 (one) itself, which is not considered prime, any positive integer is either a prime or a composite number which is the product of two of more prime factors.

---

(2006-05-25)   Euclid's Proof   (c. 300 BC)
There are infinitely many prime numbers.

It suffices to prove that there's at least one prime greater than any given prime P.

If Q is the product of all primes less than or equal to P, then any prime factor of Q+1 can't divide Q and must, therefore, be a prime greater than P. 

This proof is often  needlessly  presented as a proof by contradiction.  Too bad.

---

(2007-04-30)   Dirichlet’s theorem on primes in arithmetic progressions:
If a and N are coprime, infinitely many primes are of the form  kN+a.

This statement was conjectured by Gauss  (Euler had previously stated the special case  a = 1).  It was proved by Dirichlet in 1837, using the Dirichlet characters and related L-series which he introduced himself for that very purpose.

---

(2007-04-30)   Green-Tao Theorem   (2004)
There are arbitrarily long prime arithmetic progressions (PAP).

This was proved in 2004 by Terence Tao (1975-) and Ben Green (1977-).

In 2006 (pdf), Tao and Tamar Ziegler generalized that result and showed that the primes include arbirarily long  polynomial  progressions.  More precisely:

For any sequence of  k  integer-valued polynomials  (Q₁, Q₂ ... Q_k )  and any positive e, there are infinitely many choices of integers  x  and  m < x ^e  which make all expressions  x+mQ_i(m)  simultaneously prime.

The original Green-Tao theorem corresponds to the special case  Q_i(m) = i.

The existence of infinitely many arithmetic progressions of length 3 among primes had been established in 1939, by the Dutch mathematician Johannes van der Corput (1890-1971).  Originally, Green and Tao had set out to prove that there are infinitely many equally spaced sequences of 4 primes, but they found out that their methods prove the existence of such sequences of any length...

If  an arithmetic progression (AP) of k primes  starts above  k,  then its  common difference  (N)  must be a multiple of all the primes less than or equal to k  (or else, one such prime would be a proper factor of a term in the progression).  This is made explicit in the above, using the (fairly standard) notation  p#  to denote the  primorial  of  p,  namely the product of all primes between 2 and  p  (A002110).

The latest records are not directly relevant to the above table...  On 2004-07-24, Markus Frind, Paul Jobling and Paul Underwood found an arithmetic progression of 23 primes  (with N = 199678 . 23#,  it ends with 449924511422857) :

56211383760397  +  44546738095860 k     (k = 0 to 22).

A smaller instance was later found by Frind  (2006-04-01)  which need not be the  smallest  there is  (with  N = 9523. 23#,  it ends with 1036239621869317) :

403185216600637  +  2124513401010 k     (k = 0 to 22).

It's more difficult to find consecutive primes which happen to be in arithmetic progression.  A sequence of length 10 was first found on 1998-03-02.  Namely,  P + 210 k  (for k = 0 to 9)  with the following 93-digit value for P.

100996972469714247637786655587969840329509324689190041803603417758904341703348882159067229719

It's highly unlikely that a longer sequence (length 11) will be found any time soon, although it's conjectured that there are infinitely many instances of  k  consecutive  primes in arithmetic progression, for  any  k...

PAP   |   Ten consecutive primes in arithmetic progression

---

(2006-11-25)   PNT:  The Prime Number Theorem
A random integer N is prime with a probability roughly equal to 1/ln(N).

In 1792, at age 15, Gauss made the above statement as a private conjecture in his notebook.  This is more often stated in terms of various (asymptotically equivalent) approximations to the so-called  prime counting function  which gives the number  p(x)  of the primes that do not exceed a positive number x.  In 1808, Legendre proposed the following approximation, involving a parameter B  (about -1.08366)  sometimes known as  Legendre's constant:

p(x)   ~   x / (B + ln x)

The above conjectural remark of the young Gauss would equate   p(x)  and either flavor of the  logaritmic integral  li(x) or Li(x).  Gauss put it in this form in 1849  (although his remark appeared in print only posthumously, in 1863).  The resulting statement became known as the  prime number theorem (PNT).

p(x)	~	li(x)   ~   Li(x)
	~	x / ln(x)  +  x / (ln x)2  +  2x / (ln x)3  +  ...  +  k! x / (ln x)k+1  +  ...

The PNT is usually stated by retaining only the leading term  x/ln(x)  in the above asymptotic development of the  logarithmic integral  (although a better approximation would be obtained by retaining the first 3 terms).

Two independent proofs of this famous theorem were given simultaneously in 1896, by  Hadamard  and  de la Vallée-Poussin.  In 1951, Wiener made clear that both of those proofs rely on the established fact that the Riemann Zeta Function  z  does not have any zeroes of the form  1+it.

In 1949, a beautiful  elementary  proof of the PNT was again found by two mathematician simultaneously: Paul Erdös and Atle Selberg.

The celebrated Riemann Hypothesis  (which states that the nontrivial zeroes of  z  are all of the form  ½+it )  would be equivalent to the following statement:

p(x)   =   Li(x)  +  O(Öx ln x)

Against all available numerical evidence, which never show  p(x)  above  Li(x),  John E. Littlewood proved in 1914 that the sign of  p(x)-Li(x)  changes infinitely many times.  It's now known that the first such reversal of sign must happen for some number  x  with 370 digits or less.

n	p(n)
1	0
2	1
3	2
4	2
10	4
100	25
1000	168
10000	1229
100000	9592
1000000	78498
10000000	664579
100000000	5761455
1000000000	50847534
10000000000	455052511

---

(2006-05-24)   The Largest Known Prime
Until a fast formula is found, the record will be broken again and again.

The  largest known prime  has very often been of the form  2ⁿ-1.  Such numbers are called Mersenne numbers and their prime values are known as  Mersenne primes  (we discuss elsewhere their history, the special form of their factors and the connection with  perfect numbers).  It's easy to see that a Mersenne number can't be prime unless the exponent (n) is itself prime.  (This happens to be also a consequence of a nice general property of integer sequences which start with 0 and 1 and obey a second-order recurrence, as we demonstrate elsewhere.)  The primality of the exponent is not sufficient.  For example, the 11th Mersenne number 2047 is the product of 23 and 89, whereas the 23rd is divisible by 47...  Nevertheless, the primality of Mersenne primes is (currently) significantly easier to establish than that of all other integers of similar magnitudes.

The gap between the Mersenne primes  2¹²⁷-1  and  2⁵²¹-1  was sufficiently large to allow other approaches to break the record, as documented in the table below.

This happened again between the discovery of the primality of  2²¹⁶⁰⁹¹-1  (Slowinski, 1985)  and that of  2⁷⁵⁶⁸³⁹-1  (Slowinski, Gage et al., 1992)  when an "Amdahl 1200" computer was used to prove the primality of the following number  (J. Brown, C. Noll, B. Parady, G. Smith, J. Smith and S. Zarantonello, 1989).

391581 ´ 2 ²¹⁶¹⁹³ - 1

Since 1996, the scene has been dominated by the "Great Internet Mersenne Prime Search"  (GIMPS)  which has harnessed thousands of microcomputers and found the latest 9 record primes  (see GIMPS for an update).

The Frenchman A. Ferrier officially reported his 44-digit record-breaking prime on Bastille day, July 14, 1951.  He had been working on this since May and Jeff Miller may have been aware of Ferrier's ongoing work.  According to the 1997 recollections of "family member" David Miller  as reported by Chris Caldwell :  "Jeff Miller went to some length to make sure Ferrier's result was not overlooked ".  Miller may well have changed his original strategy (leading to his 79-digit record) specifically to beat Ferrier's upcoming result which would have overshadowed Miller's other results (the first of which broke the 75-year old record of Lucas).  However, Miller deliberately reported  both  his own 79-digit number and Ferrier's 44-digit prime as having been discovered "in early July".  This may have been a professional courtesy to Ferrier, although a deeper enquiry (which probably never took place) may or may not have revealed that Ferrier's results came a few hours too late to enter the record book.  Giving priority to Ferrier puts both numbers in the record book and still gives credit to Miller and Wheeler for having broken the long-standing record of Lucas with the earliest of their 41-digit numbers.  Ferrier's number itself stands out as the largest prime ever discovered without the help of an electronic computer.

We insist that this healthy ambiguity ought to be strictly respected now.  This is just what D.H. Lehmer did when he summarized the  "Recent Discoveries of Large Primes"  very shortly after those events  [MTAC, 5, 36, Oct. 1951].

A machine  printed  the primality of  2⁴²⁵³-1  before that of  2⁴⁴²³-1.  However, a human being  (Alexander Hurwitz)  read about the latter  before  anybody knew about the former, which was thus never largest anong "known primes"  (for more details, see our presentation of Mersenne primes and perfect numbers).

Largest Known Prime by Year  (Chris Caldwell)

---

(2007-05-08)   The Lucas-Lehmer Test
A fast way to check the primality of the  p^th  Mersenne number   2^p-1.

The Lucas-Lehmer test is a special case of the modern way to check the primality of  n  when all the prime factors of  n+1  are known.  It boils down to a procedure devised by Edouard Lucas in 1878 and simplified by D.H. Lehmer in 1930:

Consider the following recursively-defined sequence, modulo  2^p-1

L₀  =  4         L_n+1  =  L_n² - 2   [mod 2^p-1]

For an odd prime p,  2^p-1   is prime  if and only if  L_p-2  is zero.  That's all!

So, the primality of  2^p-1   can be determined with just  p-2  multiplications.

---

(2006-05-24)   Is there a formula which gives only primes?
What's a "formula" anyway?

As of this writing, checking the primality of  2^p-1  for increasingly large values of the exponent  p  is the most efficient way to name large primes  (see GIMPS).

Anything faster than that would be major news.  Something  vastly  faster could essentially end the above record-breaking game by making it easy to "name" explicitely primes with so many digits that they could not possibly be written down.  This would not necessarily end the search for primes of a specific type  (like "Mersenne primes")  but it would make the title of "largest known prime" as meaningless as that of "largest known integer"  (whatever integer is named, something like "two to the power of that" will name something vastly larger).

It's not enough to have a "formula" which gives a larger prime.  It must be an  effective  formula...

For example, there's a number  x  for which  xⁿ, truncated down to an integer, is always prime, provided only that  n  is a power of  3.  The existence of such a number  x  can be proved from the known fact (which is not too difficult to accept without proof) that there's always a prime number between a cube and the next.  We may even compute the  lowest  such  x  by bracketing its powers:

• x¹, rounded down, is the lowest prime, namely 2
• x³, rounded down, is the lowest prime between 2³ and 3³, namely 11
• x⁹, rounded down, is the lowest prime between 11³ and 12³, namely 1361
• x²⁷, rounded down, is the lowest prime between 1361³ and 1362³, etc.

All told, with  x = 2.229494772491595235722852237656-  we obtain indeed only prime values when the exponent is a power of  3, namely:  2, 11, 1361, 2521008887, 16022236204009818131831320183, etc.  The fallacy with that "etc." is, of course, that we had to prove the primality of the last value to obtain  x  with this much precision  (conversely, the precision given is barely enough to obtain this last prime number correctly).  Thus, the whole thing is merely a way to  encode  an infinite sequence of prime values into the infinitely many decimals of a real number.  It doesn't help at all in  constructing  such a sequence.

Using cubes instead of squares in the above process is most probably an overkill, but nobody has yet shown (as far as we know) that there's always a prime between a square and the next.  If it's true, then the lowest number which always yields a prime when raised to the power of a 2-power (and truncated) is  2.3247099696648664983923017-  The first (prime) values so obtained are  2, 5, 29, 853, 727613, 529420677791  and  280286254072681840639693.