# a square in a finite field of odd order

GF(q) is a finite field of order q, where q is odd.

Prove that $$a\in GF(q), a\neq0$$ has a root in $$GF(q)$$ iff $$a^{(q-1)/2}=1$$.

I tried to prove it this way:

Suppose a has a root in $$GF(q)$$, so there is some $$b\in GF(q)$$ so that $$b^2=a$$. There is a primitive element $$g$$ in $$GF(q)$$, so that $$g^x=a, g^y=b$$. Therefore $$(g^y)^2=g^x\to 2y=x$$. Furthermore $$a^{(q-1)/2}=(g^x)^{(q-1)/2}=g^{(x/2)*(q-1)}=g^{y(q-1)}$$ and since $$y$$ is an integer, $$g^{y(q-1)}=1^y=1$$.

Now suppose $$a^{(q-1)/2}=1$$, then again $$(g^x)^{(q-1)/2}=1\to g^{(x/2)*(q-1)}=1$$. That means that $$x/2$$ is an integer (or else $$g^{(x/2)*(q-1)}\neq 1$$), and therefore $$0\le x/2\le q-1$$ being an integer, $$g^{x/2}$$ creates a certain element $$b\in GF(q)$$ so that $$b^2=a$$.

I am a bit unsure of this proof - first of all since I don't use the fact that $$q$$ is odd, which means I am wrong somewhere. Second of all, I feel extremely 'weak' with my argument regarding $$x/2$$ being an integer, yet I have no idea how to strengthen it.

Any hints/directions will be extremely appreicated!

• In the second sentence of your proof, you mixed things up, $g^x = (g^y)^2$, not $(g^x)^2 = g^y$. You use that $q$ is odd because otherwise $\frac{q-1}{2}$ is not an integer. Commented Jul 29, 2014 at 14:51
• But would it matter if $x/2$ is an integer already? @DanielFischer Commented Jul 29, 2014 at 14:55
• You still have written $2x = y$, that should be $x = 2y$. I don't understand the question in your comment, you look at $a^{(q-1)/2}$. For that to make sense a priori, you need that $\frac{q-1}{2}$ is an integer. (And, by the way, if $q = 2^k$ is even, then every element of the field is a square, the Frobenius homomorphism is surjective for finite fields.) Commented Jul 29, 2014 at 15:00

The multiplicative group $\Bbb{F}_q^*$ is cyclic of order $q-1$. By the basic properties of cyclic groups this implies that squaring is bijective, when $q$ is even (more precisely, a power of two). Your claim is interesting only in the case of an odd $q$, when $2\mid q-1$. In that case it follows from the basic theory of subgroups of cyclic groups. A cyclic group $G$ of order $n$ has a unique subgroup of order $d$ for all divisor $d$ of $n$. That group consists precisely of the elements $x^{n/d}, x\in G$, or, equivalently, of the solutions of the equation $x^d=1$ in $G$. Applied to your setting this implies that the squares form the unique subgroup of order $(q-1)/2$ inside $\Bbb{F}_q^*$. Thus they are also exactly the solutions of $x^{(q-1)/2}=1$.