[FOM] Prime values of polynomials

Kreinovich, Vladik vladik at utep.edu
Thu Mar 6 10:32:33 EST 2008

You are absolutely correct. Sorry for a sloppy way I originally wrote it.  

-----Original Message-----
From: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] On Behalf Of zahidi at logique.jussieu.fr

Sorry to contradict

The set of prime numbers is NOT the range (as the variables range over the
natural numbers - or integers, that is the same) the of a polynomial with
integer coefficients. However, according to the MDPR-theorem there does
exist a polynomial such that the positive numbers in its range are the
prime numbers.


Karim Zahidi

Le Mar 4 mars 2008 18:52, Kreinovich, Vladik a écrit :
> According to Matiyasevich's theorem, every recursively enumerable set of
> natural numbers is a range of some polynomial with integer coefficients.

More information about the FOM mailing list