# Proving the undecidability of a language knowing the language of polynomials evaluating to 0 is undecidable

Knowing D={p|p is a polynomial evaluating to 0 for some assignment of integers to its variables} is not decidable, how can I prove that E={p|p is a polynomial evaluating to a prime for some assignment of integers to its variables} is not decidable?

Proving that D is mapping reducible or Turing reducible to E would be enough, since if D < E ( where < means mapping reducible), then E decidable => D decidable, and using the contrapositive we get D not decidable => E not decidable.

Is showing that D is mapping or Turing reducible to E the right approach? I don't see how it can be proved. Thanks!

Yes like you say, you have to show that an algorithm that solves $E$ can be used to solve $D$.
A practical approach is to give a polynomial $p_E$ for every polynomial $p$ such that $p$ evaluates to $0$ iff $p_E$ evaluates to a prime number.
• No, that will not work, because you first have to solve the problem itself before you assign the polynomial. Hint if $p$ is a polynomial then polynomial $2p$ will not evaluate to a prime unless under specific conditions. Commented Nov 27, 2016 at 12:34
• More precisely: $2p$ evaluates to a prime iff $p$ evaluates to $1$. (Ignoring negative thingies.) This ties "evaluating to a prime" to "evaluating to a specific value". Commented Nov 28, 2016 at 2:22