2
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Commented Jul 29, 2014 at 14:51
  • $\begingroup$ But would it matter if $x/2$ is an integer already? @DanielFischer $\endgroup$ Commented Jul 29, 2014 at 14:55
  • 1
    $\begingroup$ 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.) $\endgroup$ Commented Jul 29, 2014 at 15:00

1 Answer 1

3
$\begingroup$

No one else seems to bite, so explain this in a CW answer.

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .