# How to prove this formula for the Legendre symbol for a finite field

Let $\mathbb{F}_q$ be a finite field with $q$ odd, let $x\in\mathbb{F}_q$ and define the Legendre symbol for $\mathbb{F}_q$ as \begin{equation} \left(\frac{x}{\mathbb{F}_q} \right) = \begin{cases} \phantom{-}1 & \text{if $t^2=x$ has a solution $t\in\mathbb{F}_q^*$}\;,\\ -1 & \text{if $t^2=x$ has no solution $t\in\mathbb{F}_q$}\;,\\ \phantom{-}0 & \text{if } x=0\;. \end{cases} \end{equation}

How do I see that $$\left( \frac{x}{\mathbb{F}_q} \right) = x^{(q-1)/2}$$ as elements of $\mathbb{F}_q$? This is left as an exercise in "Elliptic Curves - Number Theory and Cryptography" by Washington but I need it in a proof and I can't seem to figure it out.

Any help is greatly appreciated.

## 1 Answer

The same proof as in Euler's criterion works fine for $\mathbb{F}_q$ because $\mathbb{F}_q$ is a field:

If $x\ne 0$, then $x^{q-1}=1$ because of Lagrange's theorem applied to the multiplicative group $\mathbb{F}_q^\times$.

Write $0=x^{q-1}-1=(x^{\frac{q-1}{2}}-1)(x^{\frac{q-1}{2}}+1)$. The map $x \mapsto x^2$ is homomorphism $\mathbb{F}_q^\times \to \mathbb{F}_q^\times$ whose kernel is $\{\pm1\}$. Therefore, the image has order $\frac{q-1}{2}$ and so there are exactly $\frac{q-1}{2}$ squares; they must be exactly the solutions of $x^{\frac{q-1}{2}}-1=0$.

• (therefore the image is a subgroup of order $\frac{q-1}{2}$) – reuns May 10 '17 at 15:29