range of a polynomial module prime nunbers I guess for every polynomial $P(x)\in\mathbb{Z}[x]$ there are infinitely many prime numbers $p$ such that 
$$\#\{P(m) \bmod p : m\in\mathbb{Z}\}\ge\frac{p+1}{2}.$$
I prove this for monomials. But I have not any idea about general situation. Any idea?
 A: Consider the polynomial
$$P(x)=x^4-5x^2+4=(x^2-1)(x^2-4)$$
We have that
$P(-x)=P(x)$ for each $x$, and so modulo any prime $p$ we see that $P(x)$ takes at most $\frac{p+1}{2}$ values modulo $p$.
But $P(-1)=P(1)=P(-2)=P(2)=0$, and so we see that $P(x)$ actually only takes at most $\frac{p-1}{2}$ values modulo $p$ for any prime $p>3$.
So the conjecture is not true in general.

Edit
We could then, of course, ask if one can classify for which polynomials the conjecture is true. This seems like a very difficult problem and I do not have any ideas on how to approach it.
I can show the following results, however:


*

*If $P(x)$ satisfies the conjecture, then so does $aP(bx+c)+d$ for any integers $a,b,c$ and $d$ such that $ab \neq 0$.


This is fairly straightforward, since as long as $p$ does not divide $ab$, $ax+d$ and $bx+c$ both just permute the elements of $\mathbb{Z}_p$.


*

*$P(x)=x^n$ satisfies the conjecture for any $n\in\mathbb{N}^+$.


This is slightly less straightforward (as far as I can tell), and I will make use of the following results:


*

*The Chinese Remainder Theorem

*Dirichlet's Theorem on primes in arithmetic progressions

*The existence of primitive roots modulo $p$ (i.e. that $\mathbb{Z}_p^*$ is cyclic)


For any $n$, we first show that there are infinitely many primes $p$ such that $\gcd(n, p-1)\leq 2$. If $n$ is odd then $\gcd(n, 2)=1$, and so by Dirichlet's Theorem, there are infinitely many primes $p$ such that $p \equiv 2 \mod n$. Then $p - 1 \equiv 1 \mod n$ and so $\gcd(n, p-1)=1$.
Now suppose that $n$ is even, and let $d$ be the largest odd divisor of $n$. Consider the following system of congruences:
$$\begin{align*}
  x \equiv 3 \mod 4\\
  x \equiv 2 \mod d
\end{align*}$$
By the Chinese Remainder Theorem, this has a unique solution $X$ modulo $4d$. Clearly $X$ and $4d$ are relatively prime, and so by Dirichlet's Theorem, there are infinitely many primes $p$ such that $p \equiv X \mod 4d$.
Such a prime $p$ has $p-1 \equiv 2 \mod 4$ and $p-1 \equiv 1 \mod d$, and so we see that $\gcd(n, p-1)=2$.
Now let $p$ be any prime such that $\gcd(n, p-1)\leq 2$ (we just showed that there are infinitely many), and let us consider the possible values of $x^n$ modulo $p$.
Let $g$ be a primitive root modulo $p$. Then any non-zero value of $x$ modulo $p$ can be written as $g^k$ for some $0 \leq k < p-1$, and so the non-zero values of $x^n$ modulo $p$ are precisely
$g^{kn}$ for some $k$. Two such values will be equal iff
$$g^{kn} \equiv g^{mn} \mod p$$
which is equivalent to
$$g^{(k-m)n} \equiv 1 \mod p$$
or
$$ p-1\mid (k-m)n $$
Since $\gcd(n,p-1)\leq 2$, we see that this implies
$$ \frac{p-1}{2} \mid (k-m) $$
and so for any $k$, there can be at most one value $m\neq k$ such that $g^{kn} \equiv g^{mn} \mod p$ (Where $k$ and $m$ are each less than $p-1$)
We see that this implies that $x^n$ takes at least $\frac{p-1}{2}$ non-zero values modulo $p$. If we then include $0$, we see that $x^n$ takes at least $\frac{p+1}{2}$ values modulo $p$, and so $x^n$ satisfies the conjecture.


*

*Any linear polynomial and any quadratic polynomial satisfies the conjecture


This final observation is effectively just a combination of the previous $2$, but some more care is taken with the quadratic case.
For the linear case, if $P(x)=ax+b$, then for any prime $p$ such that $p$ does not divide $a$ (so any prime greater than $a$, for example) we have that $P(x)$ takes all $p$ possible values modulo $p$.
For the quadratic case, let $P(x)=ax^2+bx+c$. Let $p$ be any prime which does not divide $2a$.
We can write 
$$P(x)=a\left(x+\frac{b}{2a}\right)^2+c-\frac{b^2}{4a^2}$$
Modulo $p$, this is equal to
$$a(x+m)^2+n$$
where $m \equiv b(2a)^{-1} \mod p$ and $n \equiv c-b^2(2a)^{-2} \mod p$. $2a$ has an inverse modulo $p$ since $p$ does not divide $2a$.
But $x^2$ takes exactly $\frac{p+1}{2}$ values modulo $p$, and hence so does
$(x+m)^2$, and hence also $a(x+m)^2+n$. This then implies that $P(x)$ also satisfies the conjecture. 
