3
$\begingroup$

Why is it that in $\mathbb F_q\setminus\{0\}$, when $q\neq 2^k$, there are exactly as many squares as non-squares?

My combinatorics textbook states this without proof :/

  • 5
    I hope your textbook makes an exception for the case $q=2^k$.2011-12-01
  • 0
    -checks- yep, they say "odd prime"2011-12-01
  • 0
    consider the homomorphism $F^*_{q}$ to the multiplicative group $\{+1,-1\}$, where squares are sent to $1$ and non-squares are sent to $-1$. By first homomorphism theorem, $F^{*}_{q}/ker$ is isomorphic to the image, i.e. $\{1,-1\}$, by equating the cardinality of both sets, we have the assertion.2011-12-01
  • 2
    Please try to make the body of the question self contained, even if the question was in the title, repeating it in the body is not a bad idea.2011-12-01

3 Answers 3

15

This is true if and only if $q$ is odd. Given that $q$ is odd, $\mathbb{F}_q^\times=\mathbb{F}_q\setminus\{0\}$ is an abelian group of even order (in fact it is cyclic, but we don't need to know that for this argument). Consider the squaring homomorphism $s:\mathbb{F}_q^\times\to \mathbb{F}_q^\times$, defined by $s(a)=a^2$. What is its kernel? What does that mean the size of the image must be?

  • 0
    Ooooooo clever :D thanks!2011-12-01
  • 4
    Just a quick comment: when Zev says "in fact it is cyclic, but this is not necessary", he means that it is not necessary to *know* that the group is cyclic -- one gets away by knowing what the subgroup of order $2$ elements looks like (I make arguments like this in my number theory notes to avoid existence of primitive roots until it is absolutely necessary). One definitely needs the group to **be** cyclic, or at least not an arbitrary finite abelian group of even order: for instance in $\{\pm 1\}^k$ only the identity element is a square.2011-12-01
  • 0
    @Pete: Thanks for pointing out the ambiguity; I've clarified my answer as well.2011-12-01
4

Define an equivalence relation $\sim$ on $\mathbb{F}_q^*$ with $a \sim b \Leftrightarrow a^2 = b^2 $ . The number of squares is the number of equivalence classes of this relation. Now $x^2 = y^2$ if and only if $y = \pm x $. Thus there are two elements in every equivalence class, since $x \neq -x$ for every $x \in \mathbb{F}_q^*$. Therefore there are $\frac{1}{2}|\mathbb{F}_q^*|$ equivalence classes.

EDIT: As others have noted, $q$ should be odd. In a field of order $2^k$ every element is a square: the map $x \mapsto x^2$ is then injective and thus bijective, because we're talking about finite fields here.

0

Consider the homomorphism $\phi:\mathbb F^{*}_q \rightarrow$ {$1,-1$} which sends squares to $1$ and non-squares to $-1$. You can check that it is a homomorphism. By the first isomorphism theorem we have that $\mathbb F^{*}_q/\operatorname{ker}\phi$ is isomorphic to {$-1,1$}. Since they are bijective, their cardinalities are equal hence $(q-1)/|\operatorname{ker}\phi|=2$. Hence $|\operatorname{ker}\phi|=(q-1)/2$. Since $\operatorname{ker}\phi$ is precisely the number of elements going to 1, they are precisely the squares in $\mathbb F^{*}_{q}$. Hence the number of non-squares is also $q-1-(q-1)/2= (q-1)/2$. Hence the assertion.

  • 1
    How would you show that $\phi$ is a homomorphism? I I can see that the product of two squares is a square and the product of a square and a non-square is again a non-square. How do you show that product of two non-squares is square? (I cannot use the counting argument - that if I have a non-square the products with non-squares must be remaining numbers, which are the squares - since in this way I would be using the fact, which I'm trying to prove.)2011-12-01
  • 0
    You are right..I just used the dangerous word for myself "obvious".2011-12-01
  • 1
    @MartinSleziak In $\mathbb F^{*}_{q}$ we have that $a^{q-1}=1$ for all $a$. I claim that *$a$ is a square iff $a^{(q-1/2)}=1$* If $a$ is a square then $a=x^2$ which implies $x^{2.({q-1}/2)}=x^{q-1}=1$. Now to prove the converse let $a^{({q-1}/2)}=x$ then we have that $x^{2}=1$ which has only two solutions 1 and -1. If $x=-1$ then $a^{(q-1/2)}=-1$ and if $a$ is a square,say $x^2$ then $x^{(q-1)}=-1$ which is not true. Hence the above claim is true. Now if $a$ and $b$ are two non-squares then $a^{(q-1/2)}=-1$ and $b^{(q-1/2)}=-1$ which implies $(ab)^{(q-1/2)}=1$. Hence $ab$ is a square.2011-12-01
  • 0
    What does $a^{(q-1/2)}$ mean? Of course if not every element is a square writing something like $a^{1/2}$ would not be meaningful?2016-02-08