Integer roots of integer polynomials

Let L be the language which recognizes polynomials in Z[x] (polynomials with integer coefficients) which have an integer solution. We need to show that L is in NP.

I am trying to come with up a witness with polynomial size but I can't. Checking every integer 0, 1, -1, 2, -2.... wouldn't work.

If you check 0, 1, -1, 2, -2..., then you are not using any certificate. An obvious idea is to use the root of the polynomial as a certificate.

Now we need to show that the maximal root has polynomial size compared to the polynomial. One way to do this is to use the following necessary condition for a number to be a root. If ( ) has an integer root, then this root divides . It is easy to show this. (In fact, there is a more general fact about rational roots; the first place I found it is in this PDF file, p. 4.)

As an unrelated aside, note that if we consider polynomials with arbitrary number of variables and integer coefficients, then the problem of finding out whether a given polynomial has an integer root is undecidable (Hilbert's tenth problem).