Obviously, this is not exactly true; what I am really asking is whether any diophantine polynomial equation with integer coefficients (let's call them DPEICs) who's solution does not admit contradictory results (eg, x=x+1) has a solution modulo a prime number, and more generally, whether a system of n DPEICs in n variables has a solution (again assuming noncontradictory equations). More succinctly, if a system of PEICs has a solution in the complex numbers, does it have an integer solution modulo p?

$\begingroup$ Modulo what $p$? $\endgroup$ – Mariano SuárezÁlvarez Jan 5 '13 at 18:10

1$\begingroup$ Have you looked for this problem in a number theory textbook? Every number theory textbook I have ever seen addresses this question. $\endgroup$ – Jason Starr Jan 5 '13 at 18:12

$\begingroup$ This is probably more sophisticated than you want, but using HasseWeil and some work, you should be able to do this for $p\gg 0$. For $p$ fixed, there is no reason to expect any solutions. $\endgroup$ – Donu Arapura Jan 5 '13 at 18:29

1$\begingroup$ I'm reading the question as follows: Suppose that $f_1,\ldots,f_n$ are polynomials in $n$ variables with integer coefficients, and that the $f_i$ have a common complex zero. Must there be some $n$tuple of integers $\bar{x}$ such that the greatest common divisor of the numbers $f_i(\bar{x})$ is greater than 1? Ironbeard, do you accept this formulation? $\endgroup$ – Sidney Raffer Jan 5 '13 at 19:40

1$\begingroup$ We should use this question as a canonical example of how people manage to answer interesting questions (with pretty amazing answers, even!) in trying to guess what the question really meant to ask ;) $\endgroup$ – Mariano SuárezÁlvarez Jan 6 '13 at 3:18
I assume that you're asking if there exists such a solution in $\mathbf{F}_p$ for infinitely many $p$, or for all sufficiently large $p$ under some condition (since for the single equation $x^2 + 1 = 0$ you can't hope for all large $p$ in general).
This can be solved using the Chebotarev Density Theorem and some estimates of Deligne from Weil II (as a modern replacement for the uniform LangWeil estimates for "equicharacteristic families", which I think is what Voloch and Arapura have in mind). The details below may look long, but ultimately the basic ideas are simple and the arguments are entirely standard in the subject.
Let's rephrase the question more intrinsically. Let $A$ be a finitely generated $\mathbf{Z}$algebra admitting a ring map $f:A \rightarrow \mathbf{C}$. That encodes your initial hypotheses (in a more general form), upon writing $A$ as a quotient of a polynomial ring over $\mathbf{Z}$ modulo some (finitely generated) ideal. By the Nullstellensatz over $\mathbf{C}$, the existence of $f$ just says that $A_{\mathbf{C}} := A \otimes_{\mathbf{Z}} \mathbf{C}$ is nonzero, and that in turn is equivalent to $A_{\mathbf{Q}}$ being nonzero. Your question seems to be whether for infinitely many $p$ or perhaps all sufficiently large $p$ there is a ring homomorphism $A \rightarrow \mathbf{F}_p$.
In terms of the finite type affine $\mathbf{Z}$scheme $X = {\rm{Spec}}(A)$, you're asking if nonemptiness of the generic fiber $X_{\eta}$ over $\mathbf{Q}$ forces the fiber $X_p := X \bmod p$ to have an $\mathbf{F}_p$rational point for infinitely many $p$ or (under some hypothesis on $X_{\eta}$) all sufficiently large $p$. More generally, for any finite type $\mathbf{Z}$scheme $X$ with nonempty generic fiber $X_{\eta}$ over $\mathbf{Q}$, $X_p$ has an $\mathbf{F}_p$rational point for infinitely many $p$, and even for all sufficiently large $p$ provided that $X_{\eta}$ is geometrically irreducible over $\mathbf{Q}$ (equivalently, the $\mathbf{C}$fiber $X_{\mathbf{C}}$ is irreducible, or more concretely $X_{\mathbf{Q}}$ is irreducible and $\mathbf{Q}$ is algebraically closed in the function field of $(X_{\mathbf{Q}})_{\rm{red}}$).
The existence of an $\mathbf{F}_p$point for infinitely many $p$ is a straightforward consequence of the Chebotarev Density Theorem, as follows. Choose a closed point $x \in X_{\eta}$, so its residue field $K$ is a number field. By general "spreading out" principles (ultimately just denominatorchasing in the affine case), the map $x:{\rm{Spec}}(K) \rightarrow X_{\eta}$ between respective $\mathbf{Q}$fibers of the finite type schemes ${\rm{Spec}}(O_K)$ and $X$ over ${\rm{Spec}}(\mathbf{Z})$ "spreads out" to a map ${\rm{Spec}}(O_K[1/N]) \rightarrow X_{\mathbf{Z}[1/N]}$ over $\mathbf{Z}[1/N]$ for a suitable dense open ${\rm{Spec}}(\mathbf{Z}[1/N]) \subset {\rm{Spec}}(\mathbf{Z})$. Thus, to make an $\mathbf{F}_p$point of $X_p$ for $p \nmid N$ it suffices to do the same for ${\rm{Spec}}(O_K[1/N])$, which is to say that we seek a prime ideal $\mathfrak{p}$ of $O_K$ over $p \nmid N$ at which the residual degree over $\mathbf{F}_p$ is 1. For example, it suffices to find infinitely many rational primes $p > N$ that are totally split in $K$, and the Chebotarev Density Theorem applied to the Galois closure of $K$ over $\mathbf{Q}$ provides a healthy supply of such $p$.
The deeper case is to show that $X_p(\mathbf{F}_p)$ is nonempty for all large $p$ when $X_{\eta}$ is geometrically irreducible. Note that such a hypothesis rules out cases like $X = {\rm{Spec}}(O_K)$ for a number field $K \ne \mathbf{Q}$, for which we know that the desired assertion is false. As Arapura and Voloch observe, the key input is the socalled LangWeil estimate. To make this precise (since Lang and Weil did not use the framework of "families" across varying characteristics, as their work predated the advent of schemes), we need some kind of "uniformity" in our understanding of $\#X(\mathbf{F}_p)$ as $p$ varies; this is sort of "orthogonal" to the more traditional question Weil would have asked concerning the behavior of $\#X_p(\mathbf{F}_{p^n})$ as $n$ grows with $p$ fixed.
No doubt Lang and Weil would have been able to adapt their method for "equicharacteristic families" so it applies to the "family" $f:X \rightarrow {\rm{Spec}}(\mathbf{Z})$ across varying residue characteristics, but nowadays it seems that the most efficient and elegant way to proceed is to apply Deligne's Weil II estimates, as follows. Let $d$ be the dimension of $X_{\eta}$. By general "spreading out" principles, the fibers of $f$ over some dense open ${\rm{Spec}}(\mathbf{Z}[1/M])$ are all of dimension $d$. Fix a prime $\ell$ and work over $\mathbf{Z}[1/\ell M]$ now. By the general principles in etale cohomology, the higher direct images with proper supports $R^if_{!}(\mathbf{Q}_{\ell})$ are constructible $\mathbf{Q}_{\ell}$sheaves on the etale site of ${\rm{Spec}}(\mathbf{Z}[1/\ell M])$ which vanish for $i > 2d$, and by choose a sufficiently divisible nonzero $N$ divisible by $\ell M$ we can arrange that each $R^i f_{!}(\mathbf{Q}_{\ell})$ has lisse restriction over $S = {\rm{Spec}}(\mathbf{Z}[1/N])$, say with rank $r_i$. In particular, $r_{2d} = 1$ due to the geometric irreducibility of the generic fiber, and more specifically by excision and Poincare duality we know from the geometric irreducibility (and the lisse condition over $S$) that $R^{2d} f_{!}(\mathbf{Q}_{\ell}) = \mathbf{Q}_{\ell}(d)$ as etale sheaves over $S$. Moreover, for $p \nmid N$, the GrothendieckLefschetz trace formula gives $$\#X(\mathbf{F}_p) = \sum_{i=0}^{2d} (1)^i {\rm{Tr}}(\phi_p R^i f_{!}(\mathbf{Q}_{\ell})_{\overline{\mathbf{F}}_p})$$ where $\phi_p$ denotes "geometric Frobenius" on the mod$p$ geometric stalk of $R^i f_{!}(\mathbf{Q}_{\ell})$.
In Galoistheoretic terms, this is saying $$\#X(\mathbf{F}_p) = \sum_{i=0}^{2d} (1)^i {\rm{Tr}}({\rm{Frob}}_p^{1}{\rm{H}}^i_c(X_{\overline{\mathbf{Q}}}, \mathbf{Q}_{\ell}))$$ using the natural action of ${\rm{Gal}}(\overline{\mathbf{Q}}/\mathbf{Q})$ on these cohomologies of the geometric generic fiber (which are all unramified away from $N$) with ${\rm{Frob}}_p$ an "arithmetic Frobenius" at $p$. The term for $i = 2d$ is the action of ${\rm{Frob}}_p^{1}$ on $\mathbf{Q}_{\ell}(d)$, which is $p^d$.
Now for the big input: Deligne's Weil II ensures that the $\phi_p$action on the $i$th compactly supported $\ell$adic cohomology of the geometric mod$p$ fiber has all eigenvalues (inside $\overline{\mathbf{Q}}_{\ell}$) inside the subfield $\overline{\mathbf{Q}} \subset \overline{\mathbf{Q}}_{\ell}$ and every archimedean absolute value of each of these is bounded above by $p^{i/2}$. Hence, by computing such traces as a sum of eigenvalues inside this subfield $\overline{\mathbf{Q}}$ and fixing an embedding of $\overline{\mathbf{Q}}$ into $\mathbf{C}$ (to make sense of absolute values of all of these eigenvalues at the same time) we get the estimate $$\#X(\mathbf{F}_p) \ge p^d \sum_{i=0}^{2d1} r_i p^{i/2}$$ where $r_i$ is the dimension of ${\rm{H}}^i_c(X_{\overline{\mathbf{Q}}},\mathbf{Q}_{\ell})$ (i.e., the constant rank of the lisse $R^i f_{!}(\mathbf{Q}_{\ell})$ over $S$).
This final estimate illuminates the crux of the "uniformity" as we vary $p$: the controlling factors are the ranks $r_i$ of the fibral cohomologies, the "glue" for varying $p$ being that the $i$th compactly supported $\ell$adic cohomologies of the geometric mod$p$ fibers that are relevant to the Lefschetz trace formula have a common dimension $r_i$ as we vary across the primes $p \nmid N$ (precisely because these cohomologies are the stalks of a single lisse $\ell$adic sheaf on $S$). It also illuminates the significance of the geometric irreducibility hypothesis via controlling the form of the "main term" $p^d$. (If we hadn't imposed geometric irreducibility of the generic fiber then the contribution from topdegree cohomology would have been an Artin representation controlled by the algebraic closure of $\mathbf{Q}$ in the residue fields at the generic points of $X_{\eta}$, and in this way the Chebotarev Density Theorem would intervene to account for counterexamples in the absence of the geometric irreducibility hypothesis.)
Anyway, the right side is $p^d$ minus a polynomial in $\sqrt{p}$ of degree at most $2d1$, so it is $p^d  O(p^{d1/2})$ as $p$ grows ("LangWeil"!), and hence is nonzero for $p$ sufficiently large (depending just on the $d$ and the ranks $r_i$ of the cohomologies of the geometric generic fiber).

$\begingroup$ This is a great answer! (What I had in mind was a lot more naive.) $\endgroup$ – Donu Arapura Jan 6 '13 at 14:50
The equation $X^2c=0$ with $c$ nonzero has a solution mod $p$ for only half the primes $p$. However, if the equations define an absolutely irreducible variety, then there will be a solution for all sufficiently large $p$ (by LangWeil).
Specifically, for an (absolutely irreducible) algebraic variety $V$ in $P^{n}$ of dimension $r$ and degree $d$ over a field $k$ with $q$ elements, Lang and Weil (1954) prove that $ Nq^{r} =(d1)(d2)q^{r1/2}+Aq^{r1}$ where $N$ is the number of points and $A=A(n,d,r)$ is a constant depending only on $n,d,r$. When you start with a variety over $\mathbb{Q}{}$, the $n,d,r$ are fixed, and so this clearly shows that $V$ will have points modulo $p$ for all sufficiently large $p$.
Nothing more modern is needed, and certainly not Weil II.

$\begingroup$ Are you assuming $V$ is a hypersurface? (If not, I am surprised that an invariant as coarse as the degree is sufficient.) Are you assuming $V$ is closed in the projective space? (I am surprised that one could have such a universal bound with the indicated limited dependencies on $A$ without requiring $V$ to be closed.) I tried to indicate in my answer that there's no doubt that the method of LangWeil, suitably formulated, can be applied to the problem. The thing I like about the Weil II viewpoint is that it illuminates what is happening in the error term. $\endgroup$ – user30379 Jan 6 '13 at 2:56

$\begingroup$ No, there is no need to assume that V is a hypersurface. Yes, the LangWeil result is surprisingly strong, and it only uses the Weil conjecture for curves (proved by Weil)  see their paper. $\endgroup$ – anon Jan 6 '13 at 3:06

$\begingroup$ Dear anon: OK, and $V$ doesn't need to be closed in the projective space? (I suppose "degree" might mean "degree of the closure" in that case, but it seems surprising that the kind of bound you mention would hold without something to prevent removing closed subsets from $V$.) $\endgroup$ – user30379 Jan 6 '13 at 3:41

$\begingroup$ My recollection is that they worked with projective varieties, but removing a lower dimensional subvariety is not going to change much. I suggest you look at their article  it is quite short and readable. $\endgroup$ – anon Jan 6 '13 at 4:32

$\begingroup$ @anon: I agree that a lowerdimensional excision won't change things much (in some sense), but the uniform bound you wrote seems like it might need to be reformulated to be insensitive to such excision. (And it might also be sensitive to whether the part excised is geometrically irreducible or not.) This is why I am surprised that one could have such a strong kind of uniform bound even for an "open" quasiprojective variety (which is the sort of thing I was considering in my answer). Maybe the constants depend on the "family" in that generality (as via Weil II)? I'll look at the old paper. $\endgroup$ – user30379 Jan 6 '13 at 5:38
Fermat's theorem that $a^p\equiv a\pmod p$ for any inegers $a,p$ with $p$ prime allows us to conclude that the equation $X^pX+1=0$ for any prime number $p$ does not have any solution modulo that prime number $p$..
In general, as polynomial functions and polynomials are two different animals for finite fields we have many nonconstant polynomials that are constant as functions. Actually a friend of mine used to joke that $\mathbf{Z}/2$ is an algebraically closed field: any nonconstant polynomial function over $\mathbf{Z}/2$ should assume more than one value hence it has a zero!
I believe the OP is asking about a version of Hilbert nullstellensatz, see for example these nice notes of D'Andrea.

$\begingroup$ Link in the post seems to be dead. Here is a version saved in the Wayback Machine. A new url seems to be ub.edu/arcades/atlanta.pdf (Wayback Machine.) $\endgroup$ – Martin Sleziak Aug 15 '19 at 9:07