Every element of a finite field is a sum of 2 squares?

[erogard]

Hi everyone,

I have to prove that every element z of a finite field F is a sum of 2 squares.

Really not sure how to go about proving this, though I've done some research and it is suggested to start with a function that maps F* to itself, defined by f(x) = x^{2}.

I guess if I could show some kind of surjectivity, in the sense that any z \in F can be written as z = f(a) + f(b) for some a, b in F. Well I'll post here my progresses as I keep thinking about it, but in the meanwhile any hint or suggestion would be greatly appreciated.

 

[Citan Uzuki]

First try showing that the product of (a^2+b^2) and (c^2 + d^2) is itself the sum of two squares. This tells you that the set of all nonzero numbers that can be written as the sum of two squares is a subgroup of F*. It contains the subgroup of all nonzero squares, which (away from characteristic 2) has index 2 (why?). Show the containment is proper.

 

[erogard]

First try showing that the product of (a^2+b^2) and (c^2 + d^2) is itself the sum of two squares. This tells you that the set of all nonzero numbers that can be written as the sum of two squares is a subgroup of F*. It contains the subgroup of all nonzero squares, which (away from characteristic 2) has index 2 (why?). Show the containment is proper.

Ok, I'm almost there. All I need to show now is that if we define S as the subset of F containing all the elements of F squared, then |S| = ( |E| + 1 ) /2.

but I'm not sure how to show this (otherwise I could readily conclude using an inequality relating the cardinalities of subsets of F).

 

[Dick]

Go back your original idea and define f(x)=x^2. You know that if y=x^2 then y=(-x)^2 as well. So if y has one square root then it has two (forget characteristic two for the moment). Can it have three? If y=a^2 and y=b^2 can you show a=+/-b?

 

[erogard]

Go back your original idea and define f(x)=x^2. You know that if y=x^2 then y=(-x)^2 as well. So if y has one square root then it has two (forget characteristic two for the moment). Can it have three? If y=a^2 and y=b^2 can you show a=+/-b?

Yep, pretty easily. So y has at most two square roots (well precisely 2 if y is different from 0, besides the special case for y =1). So for each element squared and its inverse squared correspond to one and the same element. That divides |F| by two, I guess. Then we must account for 0 and 1... let's see. If I take a very simple example, say with { 0, 1, -1, x, -x }, then S = {0, 1, x} whose cardinality clearly is (5+1)/2 = 3. Well I think I can argue that this holds in the general case.

Edit: (n-3)/2 plus 2 (to account for 0 and 1) = (n+1)/2. I think I got it.

The HW is due today, so I'll do it this way whether it's right or not (it's just a small part of the HW), but thanks for your contribution Dick, once again.