1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So, its basically the same argument as when I considered $\mathbb Z_p^{\times}$? $\endgroup$ – Al Jebr May 27 '16 at 0:58
  • $\begingroup$ 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. $\endgroup$ – Starfall May 27 '16 at 1:01
  • $\begingroup$ In my argument, we consider said $f$, then $f$ is a homomorphism with $ker f=\{\pm 1\}$. $\endgroup$ – Al Jebr May 27 '16 at 1:04
  • 1
    $\begingroup$ 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 $. $\endgroup$ – Starfall May 27 '16 at 1:55
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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$. $\endgroup$ – André Nicolas May 27 '16 at 0:59
  • $\begingroup$ Should that be "works equally well when q is power of an odd prime"? $\endgroup$ – Al Jebr May 27 '16 at 1:02
  • $\begingroup$ @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$. $\endgroup$ – André Nicolas May 27 '16 at 1:07
  • $\begingroup$ But a finite field only exists if $q$ is a power of prime, by a theorem by Galois. $\endgroup$ – Al Jebr May 27 '16 at 1:12
  • $\begingroup$ @AlJebr: True, and introduced quite early in most presentations. But we do not use that fact. $\endgroup$ – André Nicolas May 27 '16 at 1:14

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.