# Problem on higher order quadratic residuosity

For a prime $p$, we know cardinality of image of $Z_p$ under the map $f(x)=x^2$ is $\frac{p}{2}$. Is there any result for general polynomial like $f(x)=x^3+x$, $f(x)=x^3+x^2$ etc. ?

-

For an odd prime $p$, and the map $x^2$, the answer is $(p+1)/2$. For more complicated polynomials, things get more complicated.

The general quadratic is not much harder than $x^2$. For consider the polynomial $ax^2+bx+c$, where $a$ is not congruent to $0$ modulo the odd prime $p$. Solving the quadratic congruence $ax^2+bx+c\equiv w \pmod p$ is equivalent to solving $4a^2x^2+4abx+4ac\equiv 4aw \pmod{p}$, that is, to solving the congruence $(2ax+b)^2\equiv 4aw-4ac+b^2 \pmod {p}$ (we completed the square). For any $y$, there is a unique $x$ such that $2ax+b\equiv y\pmod{p}$. So our question reduces to finding the number of values of $w$ such that the congruence $y^2\equiv 4aw-4ac+b^2 \pmod{p}$ has a solution. There are $(p+1)/2$ values of $z$ modulo $p$ such that $y^2\equiv z\pmod{p}$ has a solution. This yields $(p+1)/2$ distinct $w$ modulo $p$ such that $ax^2+bx+c\equiv w\pmod{p}$ has a solution.

One can also get a complete answer to your question for the polynomial $x^k$. The number of "perfect $k$-th powers" modulo the odd prime $p$ is equal to $$1+\frac{p-1}{\gcd(k,p-1)}.$$ So for fixed $k$, there is wide variation in what fraction of $\mathbb{Z}_p$ is taken up by the range of $x^k$. For example, every $a$ is a cube modulo $17$, while there are only $6$ distinct cubes modulo $19$.

Unfortunately, the completing the square trick does not extend in a simple way to cubic polynomials. For instance, even though everything is a cube modulo $5$, the polynomial $x^3+x$ takes on only $2$ values modulo $5$. We can, however, get tight lower bounds on the size of the range of, for example, a cubic polynomial.

For let $P(x)$ be a fixed cubic. Then for any $r$, the congruence $P(x)\equiv r\pmod{p}$ has at most $3$ solutions. It follows that the range of $P(x)$ has cardinality at least $p/3$.

-
Thank you very much. –  user12290 Mar 26 '12 at 7:43

There's a big difference between maps of the form $x\mapsto x^k$ and more general polynomial maps.

Namely, the maps $f(x)=x^k$ are always homomorphisms of the multiplicative group $\Bbb Z_p^\times$ into itself. Coupling this with the fact that $\Bbb Z_p^\times$ is cyclic (i.e. there always exists a class $\bar a\in\Bbb Z_p$ such that every class in $\Bbb Z_p^\times$ is a power of $\bar a$) one can readily compute the number of elements in the image of $f$.

More general polynomial maps are less structured and these kind of arguments do not apply.

Of course one can use general facts about polynomials since $\Bbb Z_p$ is a field. For instance, it is immediately observed that for any $\bar a\in\Bbb Z_p$ the number of $x$ such that $f(x)=\bar a$ is at most $\deg(f)$, so that the image of $f$ must have at least $\lfloor p/\deg(f)\rfloor$ elements.

-