Power functions generating finite fields

Question

Let $q > 2$ be a prime number and consider finite field $\mathbb F_q$. I am interested in functions $f_a : \mathbb F_q \to \mathbb F_q$ defined as follows $$ f_a(x)=x^a $$

What should be a condition on $a$ (depending on $q$) so that $f_a(x)$ generates the whole $\mathbb F_q$ when $x$ iterates over $\mathbb F_q$?

For example, take $q = 7$. Then (mapping over the set) $$ f_3(\{0,1,2,3,4,5,6\}) = \{0,1,1,6,1,6,6\} \neq \mathbb F_q, $$ but $$ f_5(\{0,1,2,3,4,5,6\}) = \{0, 1, 4, 5, 2, 3, 6\} = \mathbb F_q, $$ P.S. Obviously, $a \neq 2$, because, for example $1^2 = (-1)^2$ (and $1 \neq -1$ for $q > 2$).

Answer 1

Partial answer:

It is enough to find the $a$'s for which $f_a$ is injective, because surjectivity follows as $\Bbb F_q$ is finite.

Let $a\in \Bbb N$ be such that $\gcd(a,q-1)=1$. Clearly $x^a=0$ iff $x=0$, since $\Bbb F_q$ is an integral domain. Now consider the cyclic group $\Bbb F_q^{\times}$. Let $x_0$ be a generator of $\Bbb F_q^{\times}$. Suppose $x^a=y^a$ for some $x,y\in \Bbb F_q^{\times}$. WLOG, take $x=x_0^m,y=x_0^n$ for some $1\le n\le m \le q-1$. Then, $x_0^{ma}=x_0^{na}\iff x_0^{(m-n)a}=1\implies (q-1)\mid (m-n)a$. Since $\gcd(a,q-1)=1$,we have $(q-1)\mid (m-n)$. As $0\le m-n \lt q-1$, we should have $m=n$ to avoid a contradiction.

Answer 2

This is basic theory of cyclic groups, since you’re dealing with the multiplicative group of a finite field $\Bbb F_q$, where $q$ may be any power of a prime $p$. Standard notation for this group is $\Bbb F_q^\times$.

You are asking for the $a$-th powers of the elements of the elements of $\Bbb F_q^\times$ to run through all the elements of $\Bbb F_q^\times$. Now, the enabling theorem is that $\Bbb F_q^\times$ is a cyclic group, i.e. there’s some nonzero $g\in\Bbb F_q$ such that the $q-1$ powers of $g$ run through the elements of $\Bbb F_q^\times$. (As a practical matter, it’s easy to find such a $g$).

Now, since the powers of $g$ obey the standard rules, and since $g^{q-1}=1=g^0$, we might as well forget about the particular $g$ we’re using, and deal with the exponents as integers to be read modulo $q-1$. That is, $b\equiv c\pmod{q-1}\Leftrightarrow g^b=g^c$.

Next, it’s a fundamental fact of number theory that $\gcd(a,q-1)=1$ (i.e. $a$ and $q-1$ are coprime) if and only if there are integers $A$ and $B$ such that $Aa+B(q-1)=1$. If this does happen, then $g^{Aa+B(q-1)}=g^1=g$.

But of course, that means that $g^{Aa}=g$, and thus if $z=g^c$ is any element of $\Bbb F_q^\times$, then $z=\left(g^{Aa}\right)^c=\left(g^a\right)^{Ac}$, in other words, the random nonzero $z$ is a power of $g^a$.

I’ll leave it to you to show that if $a$ and $q-1$ are not coprime, then the powers of $g^a$ don’t run through the elements of $\Bbb F_q^\times$.