An exponential diophantine representation of the set of prime numbers

The exponential diophantine representation of recursively enumerable relations is one of the fundamental steps of the solution of Hilbert’s tenth problem. Several methods for constructing exponential diophantine representations of recursively enumerable relations have been proposed in the literature. One of the main mathematical devices used by these constructions is a theorem of Kummer concerning the exponents of prime factors of binomial coefficients. This paper revisits the application of Kummer’s Theorem and defines the set of prime numbers by means of addition, multiplication, exponentiation and binomial coefficients. Then, an explicit three variable exponential diophantine representation for the set of prime numbers is obtained by exploiting a simple exponential diophantine representation for the divisibility by the powers of two of the central binomial coefficients devised by Jones and Matiyasevic. The method used in this paper can easily be generalized to obtain exponential diophantine representations for all recursively enumerable relations.