27
$\begingroup$

Meanwhile reading some introductory notes about the projective special linear group $PSL(2,q)$ wherein $q$ is the cardinal number of the field; I saw:

....in a finite field of order $q$, the number of elements ($≠0$) which are squares is $q-1$ if $q$ is even number and is $\frac{1}{2}(q-1)$ if $q$ is a odd number..." .

I can see it through $\mathbb Z_5$ or $GF(2)$. Any hints for proving above fact? Thanks.

$\endgroup$
3
  • 2
    $\begingroup$ Shouldn't that be "the number of non-zero elements that are squares..."? Because, for example, in $\mathbb{Z}/11\mathbb{Z}\,$ we have $\,6=\frac{1}{2}(11+1)\,$ squares. $\endgroup$ – DonAntonio May 30 '12 at 11:25
  • $\begingroup$ @DonAntonio: Oh Yes. I ll edit it. Thanks Don. $\endgroup$ – Mikasa May 30 '12 at 11:27
  • 1
    $\begingroup$ Nice question posed a while ago!+ $\endgroup$ – amWhy Mar 3 '13 at 0:09
20
$\begingroup$

Let $F^*$ be the multiplicative group of the field $F$. Find the kernel of the squaring homomorphism $f: F^* \to F^*$, $f(x) = x^2$. Use that to find the order of the image $f(F^*)$.

$\endgroup$
6
  • $\begingroup$ As you noted we have $Ker(f)={+1,-1}$ or $Ker(f)={+1}$. Thanks. $\endgroup$ – Mikasa May 30 '12 at 11:35
  • $\begingroup$ I personally like the question and your answer... I have a doubt..How do you differentiate for what values of $q$ kernel would be $\{+1,-1\}$ (In which case we have $\frac{q-1}{2}$ squares) and when would it be $\{1\}$ (In which case we have $q-1$ squares)... Is it because $F^*$ is group of order $q-1$ suppose $q-1$ is even then it will have an element of order $2$ which means Kernel is $\{+1,-1\}$ suppose $q-1$ is group of odd order it "may not" have an element of order $2$ :O I am a bit confused (may be more than a bit)... $\endgroup$ – user87543 Jan 5 '14 at 13:35
  • $\begingroup$ I have one more thing to say!! In general a finite group of even order have an element of order $2$ but it may not be unique.. But in our case the group is cyclic so it can not have two distinct elements of same order... (Do i have to be more careful when saying this? I guess i should) So, there would be only one element of order $2$ if $q-1$ is even and thus kernel is just $\{1,-1\}$.. But then I guess I can not say much when $q-1$ is odd... Please help me to clear this issue.. $\endgroup$ – user87543 Jan 5 '14 at 13:41
  • $\begingroup$ @PraphullaKoushik The simplest way to see this is to use the theory of polynomials; when $q$ is odd, $\pm 1$ are two distinct roots of $x^2-1$, and there can't be any more roots than that because $F$ is a domain. The proof I know of that $F^*$ is cyclic extends this same logic similarly. $\endgroup$ – Dustan Levenstein Jan 5 '14 at 15:20
  • 1
    $\begingroup$ Actually better yet, regardless of the underlying field, $x^2-1 = (x-1)(x+1)$ gives you exactly what the two roots are. Then $q$ being even or odd determines whether these roots are the same or different. $\endgroup$ – Dustan Levenstein Jan 5 '14 at 15:22
12
$\begingroup$

The multiplicative group of a finite field is cyclic.

$\endgroup$
5
  • $\begingroup$ That will do it, but what if one is not familiar with that result? $\endgroup$ – Gerry Myerson May 30 '12 at 11:23
  • 5
    $\begingroup$ @Gerry, Dustan's answer is the most elementary way, but mine works for other powers, not just squares. $\endgroup$ – lhf May 30 '12 at 11:31
  • $\begingroup$ @lhf : Sir, I like this question and you said your hint would work for more general powers and not just squares... I am thinking I am following you but could not understand on whole... Could you please help me to see more clearly... consider $\eta : F^*\rightarrow F^*$ taking $x\rightarrow x^3$ then Kernel would be collection of elements of order $3$ :O How do i go with that.. I am familiar with the statement that The multiplicative group of a finite field is cyclic.. Please help me to see how do i use this... Thank you :) $\endgroup$ – user87543 Jan 5 '14 at 13:44
  • $\begingroup$ @PraphullaKoushik, please ask a separate question. $\endgroup$ – lhf Jan 5 '14 at 13:46
  • $\begingroup$ Yes sir.. I will.. Excuse me if that bothered you :) $\endgroup$ – user87543 Jan 5 '14 at 13:47
4
$\begingroup$

Another way to prove it, way less elegant than Dustan's but perhaps slightly more elementary: let $$a_1,a_2,...,a_{q-1}$$ be the non zero residues modulo $\,q\,,\,q$ an odd prime . Observe that $\,\,\forall\,i\,,\,\,a_i^2=(q-a_i)^2 \pmod q\,$ , so that all the quadratic residues must be among $$a_1^2\,,\,a_2^2\,,...,a_m^2\,\,,\,m:=\frac{q-1}{2} $$

Note that $\,\,\forall\,1\leq i,j\leq m\,:$$$a_i+a_j=0\Longrightarrow a_i=-a_j=q-a_i\Longrightarrow$$$$\Longrightarrow a_i-a_j=q=0$$

Both left most equalities above would lead us to $\,a_i=a_j=0\,$, which is absurd.

Finally, we prove that not two of the above $\,\,(q-1)/2\,\,$ elements are equal. The following's done modulo $\,q$:$$a_i^2=a_j^2\Longrightarrow (a_i-a_j)(a_i+a_j)=0\Longrightarrow a_i-a_j=0$$since we already showed that $\,\,a_i+a_j\neq 0$

$\endgroup$
3
  • $\begingroup$ This works, when $q$ is a prime number, but how does this help, when $F$ is not a prime field? Say, when $F=GF(9)=F_3[x]/\langle x^2+1\rangle$? $\endgroup$ – Jyrki Lahtonen May 30 '12 at 12:06
  • $\begingroup$ Indeed it doesn't except when $q$ is a prime. Didn't notice before it could be a power of a prime. I'll edit my answer. Thanx. $\endgroup$ – DonAntonio May 30 '12 at 12:18
  • $\begingroup$ @DonAntonio: Thanks Don. :) $\endgroup$ – Mikasa May 30 '12 at 13:02
4
$\begingroup$

If our field is of order $2^k$, then the map $x \mapsto x^2$ is injective and thus bijective since the field is finite. Therefore every element is a square.

When the field has odd order, consider the equivalence relation on the nonzero elements defined by $x \sim y \Leftrightarrow x^2 = y^2$. The number of nonzero squares is the number of equivalence classes of this relation. Each equivalence class contains exactly two elements, so half of the nonzero elements are squares.

Intuitively, in the list of squares of nonzero elements

$$a_1^2,\ a_2^2,\ a_3^2,\ \ldots$$

we get repetitions when $a_i^2 = a_j^2 \Leftrightarrow a_i = a_j$ or $a_i = -a_j$. Since $a_i \neq -a_i$ for each $a_i$, rearranging and relabeling the list gives

$$b_1^2, (-b_1)^2, b_2^2, (-b_2)^2, b_3^2, (-b_3)^2, \ldots$$

where $b_i \neq \pm b_j$. Again, the number of different elements in this list is half the number of nonzero elements.

$\endgroup$
2
  • $\begingroup$ Why does an order of $2^k$ make $x \mapsto x^2$ injective? $\endgroup$ – Sarien Apr 29 '16 at 12:21
  • 1
    $\begingroup$ @Sarien: Then we are in characteristic $2$, so $x^2 = y^2$ implies $(x-y)^2 = 0$ implies $x = y$. $\endgroup$ – Mikko Korhonen Apr 29 '16 at 12:35
0
$\begingroup$

same thing happens in case of prime power, note that non zero elements of $F=GF(9)=F_3[x]/\langle x^2+1\rangle$ forms a mulitplicative cyclic group generated by an element say "$a$" and all even powers of a squraes and rest are non squares. Since order is $q-1$ so $(q-1)/2$ are squares. Manjit JANGRA

$\endgroup$

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.