Glossary:
Prime Pages:
Top 5000:

Euler noticed that x^{2}+x+41 takes on prime values for
x = 0,1,2,3, ... , 39; so many have asked if it is possible to have a
polynomial which produces only prime values. Sadly, it is easy to show
that this
is not the case (unless the polynomial is constant):
Theorem: A polynomial
P(z_{1},z_{2}, ..., z_{k})
with complex coefficients, which takes only primes values at nonnegative
integers, must be constant. (The same is true for algebraic functions
f(z_{1},z_{2}, ..., z_{k}).)
There are several tacks we could take from here.
We could ask what is the
most primes we can get out of a given type of polynomial (e.g., a quadratic in
one variable)? We will do that on another page (or see [Ribenboim95,
chapter 3]). Another approach might be to ask if there is a nonconstant polynomial all
of whose positive values (as the variables range in the set of
nonnegative integers) are all primes. Matijasevic showed this was possible in
1971 [Matijasevic71], and in 1976 Jones, Sato, Wada and Wiens gave the
following
explicit example of such a polynomial with 26 variables (and degree 25).
(k+2){1  [wz+h+jq]^{2} 
[(gk+2g+k+1)(h+j)+hz]^{2}
 [2n+p+q+ze]^{2}  [16(k+1)^{3}(k+2)(n+1)^{2}+1f^{2}]^{2}
 [e^{3}(e+2)(a+1)^{2}+1o^{2}]^{2}
 [(a^{2}1)y^{2}+1x^{2}]^{2}
 [16r^{2}y^{4}(a^{2}1)+1u^{2}]^{2}
 [((a+u^{2}(u^{2}a))^{2 }1)(n+4dy)^{2}
+ 1  (x+cu)^{2}]^{2}  [n+l+vy]^{2}
 [(a^{2}1)l^{2}+1m^{2}]^{2}
 [ai+k+1li]^{2}  [p+l(an1)+b(2an+2an^{2}2n2)m]^{2}
 [q+y(ap1)+s(2ap+2ap^{2}2p2)x]^{2}
 [z+pl(ap)+t(2app^{2}1)pm]^{2}}
Notice that this polynomial factors! Look at the special form of the
second part: it is one minus a sum of squares, so the only way
for it to be positive is
for each of the squared terms to be zero (this is a trick of
Putnam's).
Challenge: Can you find a values (a,b,c,d,...,z) (all
nonnegative) for which the polynomial above is positive?
The record for the lowest degree of such a polynomial is 5
(with 42 variables
[JSWW76]), and the record for fewest variables is 10 (with degree about 1.6^{.}10^{45}
[Matijasevic77]).
See Also: FormulasForPrimes References:
 JSWW76
 J. P. Jones, D. Sato, H. Wada and D. Wiens, "Diophantine representation of the set of prime numbers," Amer. Math. Monthly, 83 (1976) 449464. MR 54:2615
 Matijasevic71
 Y. V.Matijasevic, "A Diophantine representation of the set of prime numbers (in Russian)," Dokl. Akad. Nauk SSSR, 196 (1971) 770773. English translation by R. N. Goss, in Soviet Math. Dokl., 12, 1971, 249254.. MR 43:1921
 Matijasevic77
 Y. V. Matijasevic, "Primes are enumerated by a polynomial in 10 variables (in Russian)," Zapiski Sem. Leningrad Mat. Inst. Steklov, 68 (1977) 6282, 144145. English translation by L. Guy and J. P. Jones, J. Soviet Math., 15, 1981, 3344.. MR 58:21534
 Ribenboim95
 P. Ribenboim, The new book of prime number records, 3rd edition, SpringerVerlag, New York, NY, 1995. pp. xxiv+541, ISBN 0387944575. MR 96k:11112 [An excellent resource for those with some college mathematics. Basically a Guinness Book of World Records for primes with much of the relevant mathematics. The extensive bibliography is seventyfive pages.]
