Does there exist polynomial $p(x)$ with integer coefficients such that $p(x) > 0$ for all real values of $x$, but for any integer $n > 0$ there exists integer $k$ such that $n$ divides $p(k)$? The trick with multiplying quadratic polynomials (as here Diophantine equation with no integer solutions, but with solutions modulo every integer) does not work, if I am not mistaken.

1$\begingroup$ Yes: $(2x1)^2(x^2+7)$, if I'm not mistaken. The former factor deals with the odd factors of $n$ and the latter with the powers of 2. $\endgroup$ – Kevin Buzzard Nov 26 '10 at 21:52

2$\begingroup$ @Kevin: If $x=1/2$, $p(x)=0$. It is supposed to be $\gt 0$ for all $x$. $\endgroup$ – Mark Sapir Nov 26 '10 at 21:54

$\begingroup$ Aie! Yes, I've just made it positive for all integer values of $x$. Thanks Mark. $\endgroup$ – Kevin Buzzard Nov 26 '10 at 22:24

2$\begingroup$ A related error: $(x^22)^2(x^217)^2(x^234)^2$ is positive for all rational values of $x$ and has a root mod $n$ for all positive integers $n$. $\endgroup$ – Kevin Buzzard Nov 26 '10 at 22:32
$\newcommand{\Q}{\mathbf{Q}}\newcommand{\Z}{\mathbf{Z}}$ I now suspect the answer might be no! This isn't a complete answer but it might be an idea that turns into one.
So let me assume that such $p$ exists and let me go for a counterexample.
First I claim that if such $p$ exists, then a monic $p$ exists. For if $p$ works, then so does $Np$ for a large positive integer $N$, and if $p=cx^d+\ldots$ and $N=c^{d1}$ then $Np=q(cx)$ with $q$ monic with integer coefficients, and $q$ also works. So WLOG $p$ is monic.
Now say $p$ factors as $p_1p_2\ldots p_r$ in $\Q[x]$ with the $p_i$ monic. By Gauss' Lemma the $p_i$ are all in $\mathbf{Z}[x]$. Note that $p$ must have positive degree so $r\geq 1$. Let $K$ be the splitting field of $p$ and let $K_i$ be the field $\Q[x]/(p_i)$. Now none of the $K_i$ have any real places. Let $c$ denote any complex conjugation in $Gal(K/\Q)$. By Cebotarev density, there's a prime number $\ell$, unramified in $K$, and such that $Frob_\ell$'s conjugacy class in $Gal(K/\Q)$ is that of $c$, and indeed there are infinitely many such $\ell$.
Certain primes cause me trouble, so let me get rid of them now: for each $K_i$ let $S_i$ be the index of $\Z[x]/(p_i)$ in the full ring of integers of $K_i$, and let $S$ be the product.
Now let $\ell$ be a prime as above, and such that $\ell$ doesn't divide $S$. I claim that this $\ell$ is going to cause us problems. Say $p(k)$ is zero mod $\ell$. Then one of the $p_i(k)$ is zero mod $\ell$, so the factorization of $p_i$ mod $\ell$ has a linear factor, and so $\ell$ factors in the integers of $K_i$ into a bunch of primes one of which has degree 1. I now want to argue something like the following: the Frobenius element at $\ell$ corresponding to this prime is fixing a root of $p_i$ so complex conjugation is fixing a root of $p_i$ so $p$ has a real root! But the cricket has just started and I can't think straight. Can this be turned into a proof?

15$\begingroup$ Dear Kevin, Here is a rephrasing of your argument, which just makes it a little more succinct: suppose that $p(x)$ has a root modulo a density one set of primes. Then by Cebotarev density every element of $G$ (the Galois group of the splitting field of $p(x)$) has a fixed point in the action on the roots. In particular, complex conjugation does, and so $p(x)$ has a real root. Cheers, Matt $\endgroup$ – Emerton Nov 27 '10 at 1:57

1$\begingroup$ By the way, just as a minor remark, there's nothing special about the real completion of $\mathbf{Q}$ in the argument using the weaker hypothesis as in Matt's comment. That is, if $K/\mathbf{Q}$ is a splitting field of $p(x)$ and $\ell$ is any prime unramified in $K$ then ${\rm{Frob}}_{\ell} \in {\rm{Gal}}(K/\mathbf{Q})$ coincides with ${\rm{Frob}}_{\ell'}$ for some $\ell'$ in the density1 set and hence has a fixedpoint when acting on the set of roots. So $p(x)$ also has a root in the $\ell$adic completion of $\mathbf{Q}$. $\endgroup$ – BCnrd Nov 27 '10 at 6:09

1$\begingroup$ @Emerton: For some reason I was scared about working in $K$ but it seems that I shouldn't have been. Frictionless: because I'm in the UK I only listened for 30 minutes, during which it sounded like we were all over them, then went to bed, so I missed the real grimness :) $\endgroup$ – Kevin Buzzard Nov 27 '10 at 11:17

$\begingroup$ Did you only just post now because you thought you'd get the 300 runs needed in the last 41 overs ;) $\endgroup$ – Kevin Buzzard Nov 29 '10 at 7:24