**Guess :** What property do these polynomials have in common ? (hint : it has something to do with prime number production)

P_{2}(X) = X^{2} + X + 2

P_{3}(X) = X^{2} + X + 3

P_{5}(X) = X^{2} + X + 5

**Answer :** P_{k}(X) is prime for X=0, 1 ... k-2. Indeed, P_{2}(0) = 2, P_{3}(0) = 3, P_{3}(1) = 5, P_{5}(0) = 5, P_{5}(1) = 7, P_{5}(2) = 11, P_{5}(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 P_{k} has this property ?

You can find two more suitable polynomials, P_{11} and P_{41}, 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. P_{41} 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, P_{k}(X) = X^{2} + X + k. Those assertions are equivalent :
- q = 2, 3, 5, 11, 17, 41
- P
_{k}(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 P_{41} 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 * X^{2} - 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