Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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. ?

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

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$.

share|improve this answer
    
Thank you very much. –  user12290 Mar 26 '12 at 7:43
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.