Guess : What property do these polynomials have in common ? (hint : it has something to do with prime number production)
P2(X) = X2 + X + 2
P3(X) = X2 + X + 3
P5(X) = X2 + X + 5
Answer : Pk(X) is prime for X=0, 1 ... k-2. Indeed, P2(0) = 2, P3(0) = 3, P3(1) = 5, P5(0) = 5, P5(1) = 7, P5(2) = 11, P5(3) = 17.
A common competition between mathematicians is to beat records, and since prime number computations are time consuming this field is beloved by researchers. Here is a nice one : what is the greatest integer k such that Pk has this property ?
You can find two more suitable polynomials, P11 and P41, in a reasonable amount of time. In fact Leonhard Euler had already found those but he could neither find any other greater than 41, nor prove whether it is or not a record. P41 is called Euler's polynomial.
Until recently this problem was still open. But in 1967, H.M.Stark proved the following theorem :
Theorem :
k prime number, Pk(X) = X2 + X + k. Those assertions are equivalent :
- q = 2, 3, 5, 11, 17, 41
- Pk(n) is prime for n=0, 1, ..., k-2
- Q(sqrt(1-4q)) has class number 1
This means that 41 is the record. Euler can be proud because his polynomial P41 is the ultimate winner of the competition and it will never be defeated.
The proof for this theorem is quite complex. It has to do with quadratic fields. Q(sqrt(1-4q)) is the set of numbers of the form a + b*sqrt(1-4q) where a and b ∈ Q. An interesting thing to note is that Q(sqrt(1-4q)) is a vector subspace of C and that 1-4q = 1 mod 4.
Euler's polynomial has been beaten by another quadratic polynomial but (of course) it is not of the same form : P(X) = 36 * X2 - 810*x + 2753 which produces 45 primes, for x = 0 to 44. I do not know who to give credit for this discovery.
Generating prime numbers is as hard as primality testing because most of the time algorithms used only yield integers that have a high probability of being prime and they must be tested afterwards. Up to today, there is no simple formula to produce prime numbers.
Sources : My numbers, my friends Paulo Ribenboim
fr.sci.maths