Whether the map $x\mapsto x^3$ in a finite field is bijective

Question

Suppose $p\in\mathbb{Z}$ is prime and $\mathbb{F}_p:=\mathbb{Z}/p\mathbb{Z}$ is the finite field of size $p$. Now, consider the map: $$f:\mathbb{F}_p \to \mathbb{F}_p$$ given by $f(x)=x^3$. Then,

(1) What are the values of $p$ for which $f$ is bijective ?

(2) What are the values of $p$ for which $f$ is injective/surjective ?

EDIT: I came up with this problem while I was trying to count the number of solutions $x^3+y^3=z^3$ over $\mathbb{F}_p$. Now, if we can show that $x\mapsto x^3$ is bijective, then this reduces to count the number of solutions of $x+y=z$, which is relatively easy. And injectivity or surjectivity would have given some bounds on the number of solutions in terms of the the number of solutions of the latter.

Answer 1

A map between finite sets of same cardinality is injective, iff its bijective, iff its surjective. So $(1)\Leftrightarrow (2)$.

Also $f(0)=0$. Hence, it suffices to examine surjectivity on $\mathbb F_p^*$. Since this group is cyclic, we have a primitive root $g$.

• $3\nmid p-1$: Let $y=g^k\in\mathbb F_p^*$ for some $k\in\mathbb Z$. Then we can choose an $m\in\mathbb Z$ (in fact $m\in\{0,1,2\}$), such that $3\mid k+m(p-1)$. Set $$x=g^{\frac{k+m(p-1)}{3}}$$ and verify $x^3=y$.
• $3\mid p-1$: Assume, there is a $x$, such that $x^3=g$, set $x=g^k$ for some $k\in\mathbb Z$, then $g^{3k}=g$, so $p-1\mid 3k-1$, hence $3\mid 3k-1$, a contradiction.

Answer 2

We always have $f(0)=0$, and that this is the only zero of $f$, so it suffices to study the restriction of $f$ to the non-zero elements, i.e. the multiplicative group.

Hints (both related to both parts of your question):

1. We see that $f$ is a homomorphism from the multiplicative group to itself.
2. It is known that the said multiplicative group is cyclic of order $p-1$, so you are well advised to recall what you know about endomorphisms of cyclic groups. Most notably what you know aboout the kernels of those homomorphisms and the relation between the respective sizes of the kernel and the image.

Answer 3

It is easy to prove that $f(0)=0$ and that $f$ restricts to a homomorphism $\mathbb{F}_p^{\times} \rightarrow \mathbb{F}_p^{\times}$. Bijectivity of $f$ is equivalent to bijection on the multiplicative group.

Now we split into two cases (the idea is to consider when we can/can't invert $3 \bmod p$):

1) $3\nmid p-1$. In this case $a = 3^{-1} \bmod p-1$ exists and you can check the map $x \mapsto x^a$ is the inverse of $f$ hence in this case we have a bijection.

2) $3 \mid p-1$. In this case we must invoke a primitive root $g$ in $\mathbb{F}_p^{\times}$. Since $g^{\frac{p-1}{3}} \neq 1$ we find that $f(g^{\frac{p-1}{3}})=(g^{\frac{p-1}{3}})^3 = 1 = f(1)$, hence $f$ is not injective in this case, hence not surjective (since we have a map of finite sets), hence not bijective.

Answer 4

Following Tomas's suggestion, I am posting this as an answer:

I encountered this problem while directing a Master's thesis two years ago, and again (in a different setting) with another thesis last year. I seem to recall that I somehow got to this while reading slides of a talk by Paul Pollack. Anyway, I like to deduce the results asked in the problem from quadratic reciprocity: First, $f$ is the identity when $p=3$. From now on, assume $p\ne 3$. It suffices to prove that $p\equiv −1\pmod 3$ iff $f$ is injective. This is clear if $p=2$, so we may assume $p$ is odd. Also, if $x,y\in\mathbb F_p$, $x\ne0$, and $x^3=y^3$, then $\displaystyle\left(\frac xy\right)^3=1$, so it suffices to show that for $p$ odd prime, $x^3=1$ has only one solution iff $p\equiv−1\pmod 3$.

Now, $x^3=1$ if $x=1$ or $x^2+x+1=0$. The second option is equivalent to $(2x+1)^2+3=0$, so there are non-trivial solutions iff $−3$ is a quadratic residue modulo $p$. Now apply quadratic reciprocity: $$\displaystyle \left(\frac{−3}p\right)=\left(\frac{−1}p\right)\left(\frac 3p\right)=(−1)^{\frac{p−1}2}(−1)^{\frac{p−1}2\cdot\frac{3−1}2}\left(\frac p3\right), $$ and the result follows, since $\displaystyle \left(\frac p3\right)=p\pmod 3$.

By the way, the OP's application to counting the number of solutions of $x^3+y^3=z^3$ is a natural one. For more on the number of solutions of $x^q+y^q=z^q$, this was studied by Dickson in 1909; see lecture 12 in

Paulo Ribenboim. 13 Lectures on Fermat’s Last Theorem, Springer-Verlag, New York-Heidelberg, 1979. MR0551363 (81f:10023).

You may also want to look at Chapter 6 of my student Summer Kisner's thesis, mentioned above, and at the references discussed there.

Let me close by briefly mentioning the setting in which my student Thomas Chartier and I ran into this result while working on his thesis. Tommy was studying a nice problem (still open) that originated on MO, see here. The question is whether, for any $n\in\mathbb Z^+$, there is a coloring of the positive integers such that, for any $a$, the numbers $a,2a,\dots,na$ all receive different colors.

There is an easy such coloring if $n+1$ is prime: Say $n+1=p$. Write $a$ as $kp^t$ where $p$ does not divide $k$, and assign to $a$ the color $k\pmod p$. There is also an easy coloring if $2n+1$ is prime: say $n+1=p$. As before, write $a=kp^t$. Now assign to $a$ the color $k^2\pmod p$.

A generalization is easy: If $nl+1=p$ is prime, and $1^l,2^l,\dots,n^l$ are all distinct modulo $p$, then we assign to $a=kp^t$ the color $k^l\pmod p$. It is the second condition (that $1^l,\dots,n^l$ are distinct modulo $p$) that is hard to verify (and automatic if $l=1$ or $l=2$). In fact, for any $l>2$ there are only finitely many $n$ such that $nl+1$ is prime and the second condition is verified. For $l=3$, there are no such $n$, and the proof of this is essentially the result this question asked about, what one shows is that if $3n+1=p$ is prime, then there is an $i$ with $2<i\le n$ such that $i^3\equiv 1$ or $i^3\equiv 8\pmod p$.

(For this and additional related results, see Chapter 5 of Tommy's thesis, and this MO question.)

Answer 5

The nonzero elements form a group of order p-1, which has an element of order three iff p-1 is divisible by 3.