Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 :/

share|improve this question
5  
I hope your textbook makes an exception for the case $q=2^k$. –  Gerry Myerson Dec 1 '11 at 6:19
    
-checks- yep, they say "odd prime" –  badatmath Dec 1 '11 at 6:32
    
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. –  Dinesh Dec 1 '11 at 7:47
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. –  Asaf Karagila Dec 1 '11 at 11:33
add comment

3 Answers

up vote 12 down vote accepted

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?

share|improve this answer
    
Ooooooo clever :D thanks! –  badatmath Dec 1 '11 at 6:31
    
Thanks, glad to help! –  Zev Chonoles Dec 1 '11 at 6:33
3  
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. –  Pete L. Clark Dec 1 '11 at 7:33
    
@Pete: Thanks for pointing out the ambiguity; I've clarified my answer as well. –  Zev Chonoles Dec 1 '11 at 7:47
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
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.) –  Martin Sleziak Dec 1 '11 at 8:11
    
You are right..I just used the dangerous word for myself "obvious". –  Dinesh Dec 1 '11 at 8:29
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. –  Dinesh Dec 1 '11 at 8:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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