# Sum of two squares mod p using primitive root

My question is as follows (Problem 5.2 in Aluffi, Algebra: Chapter 0):

Question. For any finite field $$F := \mathbb{F}_{p^d}$$, show that any element $$k$$ can be written as a sum of two squares, i.e. there exists $$x,y\in F$$ such that $$k = x^2 + y^2$$.

I am wondering if there is a solution using primitive elements of the field $$F$$, as suggested by Aluffi in the hint.

The same question has been asked here, here, and here. However, all of the given answers are combinatorial (using Pigeonhole Principle), and they are not what I am looking for.

• Some related material here. Rehashing the ideas. A) It suffices to show that some non-square $n\in F$ is a sum of two squares, because every non-square has the form $(g^a)^2n$, where $a$ is a natural number and $g$ is a primitive element. B) Mikhail Ivanov's argument settles the case of prime fields as follows: Let $n$ be the smallest quadratic non-residue modulo $p$. Then $n-1$ is a quadratic residue and $n-1=x^2$. So $n=x^2+1$ is a sum of two squares and we are done by part A. Jul 6, 2022 at 3:38
• (cont'd) Alas, I don't see a way to tweak the argument in B to work for non-prime fields also. I suspect something along these lines works, but... Jul 6, 2022 at 3:40
• Anyway, there are $(p^d+1)/2$ squares in $F$, so they cannot form an additive subgroup (Lagrange). Therefore some sum of two squares is a non-square, and the argument A) kicks in. Leaving this as a comment for now, because I'm not sure that this is what you are looking for? It does not really use a primitive element. After all, we only the fact the ratio of two non-squares in $F$ is a square for the argument A to work. Jul 6, 2022 at 3:46
• Last but not least: $\huge{+1}$ for having searched the site before asking. If everybody did that, the site would be much better off! Jul 6, 2022 at 3:48