Does every polynomial diophantine equation have solutions modulo p? 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 non-contradictory equations).
More succinctly, if a system of PEICs has a solution in the complex numbers, does it have an integer solution modulo p?
 A: The equation $X^2-c=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 Lang-Weil).
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 $| N-q^{r}| =(d-1)(d-2)q^{r-1/2}+Aq^{r-1}$ 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.
A: 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 Lang-Weil estimates for "equi-characteristic 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 non-emptiness 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 non-empty 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 denominator-chasing 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 non-empty 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 so-called Lang-Weil estimate.  To make this precise (since Lang and Weil did not use the framework of "families" across varying characteristics, as their work pre-dated 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 "equi-characteristic 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 Grothendieck-Lefschetz 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 Galois-theoretic 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}^{2d-1} 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 top-degree 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 $2d-1$, so it is $p^d - O(p^{d-1/2})$ as $p$ grows ("Lang-Weil"!), 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).
A: 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^p-X+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 non-constant polynomials that are constant as functions. 
Actually a friend of mine used to joke that $\mathbf{Z}/2$ is an algebraically closed field:
any non-constant polynomial function over $\mathbf{Z}/2$ should assume more than one value hence it has a zero!
A: I believe the OP is asking about a version of Hilbert nullstellensatz, see for example these nice notes of D'Andrea.
