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