4
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.