  The undecidability of the additive theory of primes (with identity) as well
as the theory Th(N,+, n -> p\_n), where p\_n denotes the (n+1)-th prime, are
open questions. As a possible approach, we extend the latter theory by adding
some extra function. In this direction we show the undecidability of the
existential part of the theory Th(N, +, n -> p\_n, n -> r\_n), where r\_n is
the remainder of p\_n divided by n in the euclidian division.
