# Finding square roots of quadratic residues in prime power field

I know that in fields of cardinality $$p$$, $$a$$ is a quadratic residue if and only if $$a^{\frac{p-1}{2}}=1$$ (Euler's criterion). Therefore $$a^{\frac{p+1}{2}}=a$$ and if also $$p=3\!\!\!\mod\! 4$$ we can exhibit the square roots: $$(a^{\frac{p+1}{4}})^2=a$$.

Can we do something similar in fields of prime power cardinality (i.e., find square roots of elements with possibly a constraint on the cardinality)? I do not see how trying to do the same thing with the Legendre symbol helps.

This question was marked as a possible duplicate of Quadratic residues in finite field, however, I'm not asking whether an element is a quadratic residue, but assuming it is a quadratic residue, obtain its square roots.

Yes, we can. That criterion and the formula for the square root work because the multiplicative group of integers mod $$p$$ is cyclic (of order $$p-1$$). Well, the multiplicative group of the field of cardinality $$p^k$$ is cyclic as well (of order $$p^k-1$$).
Thus, for $$p>2$$, $$a$$ is a square in the field of order $$p^k$$ if and only if $$a^{(p^k-1)/2}=1$$ or equivalently $$a^{(p^k+1)/2}=a$$. For $$p\equiv 3\mod 4$$ and $$k$$ odd, we also have explicit square roots $$\left(a^{(p^k+1)/4}\right)^2=a$$.
What about $$p=2$$? In those fields, everything is a square, and the map $$x\to x^2$$ is a field automorphism.
• The Euler criterion follows from the group being cyclic. Saying $(b^2)^{|G|/2}=e$ works in any finite group $G$, while the converse that $a$ is a square if $a^{|G|/2}=e$ requires an additional condition on the structure of $G$ - like being cyclic. – jmerry Feb 9 at 21:27
• I see your point but still do not understand the implicance. According to Euler's theorem, we have $$a^{p^{k-1}(p-1)}=1\mod p^k,$$ because of the multiplicativity of the totient function. Doesnt this mean that the roots are given by $$a^{\frac{p^{k-1}(p-1)+1}{2}}?$$ – Tal-Botvinnik Feb 11 at 11:40
• Why are you asking about things mod $p^k$ now? We're working with finite fields of characteristic $p$ - that's not the same structure. – jmerry Feb 11 at 11:43