# In $GF(q)$, are there the same number of quadratic residues as quadratic nonresidues?

I know that for $\mathbb Z_p^*$ (the multiplicative group of a field with $p$ elements where $p$ is a prime), there are $(p-1)/2$ quadratic residues, and thus $(p-1)/2$ quadratic nonresidues. We can see this by considering $f:\mathbb Z_p^* \longrightarrow \mathbb Z_p^*$, defined by $f(\bar x)=\bar x^2$, where $\bar x$ is a least non-negative residue. But what about for the general finite field with $q$ elements $GF(q)$, where $q$ is a power of $p$?

Are there the same number of quadratic residues as nonresidues? How would I go about showing this?

For the multiplicative group of a finite field $K$, the mapping $f(x) = x^2$ is an endomorphism whose kernel is $\{ 1, -1 \}$, which means the image $N$ of $f$ is a subgroup with index 2, which means the quotient $K^{\times}/N$ has $2$ elements. Now, let $h : K^{\times} \to K^{\times}/N$ be the quotient epimorphism. This epimorphism maps every quadratic residue in $K$ to $N$, and since it cannot map a nonresidue to $N$, it maps it to the other coset of $N$. The result follows from the fact that the cosets of a subgroup have the same cardinality.

Note: If $K$ has characteristic $2$ then $1 = -1$, so the kernel of $f$ really has only one element. Every element is a quadratic residue in these fields.

• So, its basically the same argument as when I considered $\mathbb Z_p^{\times}$? – Al Jebr May 27 '16 at 0:58
• I don't know your argument, since you do not specify how we consider $f(x) = x^2$, but if you meant what I said; then yes. – Starfall May 27 '16 at 1:01
• In my argument, we consider said $f$, then $f$ is a homomorphism with $ker f=\{\pm 1\}$. – Al Jebr May 27 '16 at 1:04
• The quotient epimorphism is given by $h(x) = xN$, and since $N$ contains all quadratic residues by definition, we have that $x \in N$ and therefore $xN = N$. – Starfall May 27 '16 at 1:55

The argument that works when $q$ is an odd prime works equally well in a $q$-element field where $q$ is odd.

For any non-zero $x$ in our field, let $f(x)=x^2$. Note that $f(x)=f(-x)$. We show that conversely if $f(t)=x^2$, then $t=\pm x$. For if $t^2=x^2$, then $t^2-x^2=0$, so $(t-x)(t+x)=0$. Since we are working in a field, it follows that $t=x$ or $t=-x$. Since $q$ is odd, we have $x\ne -x$.

Thus the function $f$ is two-to-one, and the result follows in the same way as in the case $q$ is an odd prime.

• @Starfall: It is a proof of exactly the same fact as the one you proved, in a style somewhat closer to the one given by OP for $\mathbb{Z}_p^\ast$. – André Nicolas May 27 '16 at 0:59
• Should that be "works equally well when q is power of an odd prime"? – Al Jebr May 27 '16 at 1:02
• @AlJebr: I could have said that, and did initially. I rephrased it by instead talking about a field with $q$ elements where $q$ is odd, since only field properties are being used. The (kind of silly) reason to avoid it is that for the proof we really do not need to know the fact that $q$ must be a power of an odd prime, all we need to know is that if $x\ne 0$ then $x\ne -x$. – André Nicolas May 27 '16 at 1:07
• But a finite field only exists if $q$ is a power of prime, by a theorem by Galois. – Al Jebr May 27 '16 at 1:12
• @AlJebr: True, and introduced quite early in most presentations. But we do not use that fact. – André Nicolas May 27 '16 at 1:14