# Thread: Finite field

1. ## Finite field

Show that every element in a finite field can be written as the sum of two squares.

2. you do this yourself --

1. consider $\displaystyle F^*$. prove that at least half of its elements are squares.
2. from this you conclude your result.

3. Originally Posted by nirax
you do this yourself --

1. consider $\displaystyle F^*$. prove that at least half of its elements are squares.
2. from this you conclude your result.
yeah....I know but I'm sorry that I just have no idea how to get 2 from 1...

4. ok i will give u one more hint. suppose exactly half of them are squares (when is this the case ? when it is not ?) then the squares form an index 2 subgroup of F^*. the squares you can write as 0+a^2 .. suppose some element is not expressible as sum of two squares, then what happens if you take the squares and take the additive group generated by them ? if you add 0 to that set, will it become a subfield ? if so, what should be its cardinality ?

5. hmm...I am sorry that i cannot understand your idea..
if one element can not be written as the sum of two squares, it does not mean it will not be in the additive group generated by the squares since it may be the sum of three squares..
if it is in the additive group generated by the squares, then the group will be the original group since its order is greater than the half of the original order..then nothing would happen??
May be there are some mistakes in above statements..but I am just confused...

6. call $\displaystyle A$ as the multiplicative group of squares. so we decompose $\displaystyle F = A \cup \{0\} \cup B$. $\displaystyle B$ is the set of non squares. suppose an element $\displaystyle a$ is not expressible as sum of two squares. consider $\displaystyle a - A$. this set must be the same as $\displaystyle B$. consider $\displaystyle x = a - a^2$. clearly $\displaystyle x \in B$

but $\displaystyle B$ was the coset of the multiplicative group $\displaystyle A$ in $\displaystyle F^*$. so $\displaystyle B = a.A$. it follows that there exists a $\displaystyle y$ s.t

$\displaystyle x = a.y^2 = a - a^2$

$\displaystyle \Rightarrow a (y^2 - 1 + a) = 0$
$\displaystyle \Rightarrow y^2 = a - 1$

RHS belongs to $\displaystyle B$ whereas LHS belongs to $\displaystyle A$ which are disjoint.

7. why a+A=B?
if we use contrapositive proof, suppose a+b^2=c^2, then a=c^2-b^2...no contradiction..
if a+b^2=0, then a=-b^2,any contradiction?
-b^2 is a square, or not?

8. Originally Posted by ynj
why a+A=B?
if we use contrapositive proof, suppose a+b^2=c^2, then a=c^2-b^2...no contradiction..
if a+b^2=0, then a=-b^2,any contradiction?
-b^2 is a square, or not?
a+A must be the same as B else it intersects with A then a wud be expressible as sum of two squares. also note that A and B are equicardinal. -b^2 may not be a square as -1 is not a square in all fields.

9. for example in $\displaystyle F_7$, $\displaystyle -1$ is not a square. whereas it is a square in all characteristic 2 fields.

10. Originally Posted by nirax
a+A must be the same as B else it intersects with A then a wud be expressible as sum of two squares.
hmm...would you please explain it in detail? In my previous post, I actually try to prove a+A=B. but we get a=b^2-c^2,not a=b^2+c^2!!

11. Note that A is multiplicative group,not a additive group...So a+A is not a coset..

12. Originally Posted by ynj
hmm...would you please explain it in detail? In my previous post, I actually try to prove a+A=B. but we get a=b^2-c^2,not a=b^2+c^2!!
see ...

a + A has the same cardinality as A as well as B. also it cannot contain 0 as a is not a square. so it follows that a + A must either be B or A or in intersects with both. in the last two cases if it intersects nontrivially with A, it means there exist an element z^2 in A such that a + y^2 = z^2, but this is a contradiction to what we assumed about a.

edit :: this is erroneous, proof corrected above

13. Originally Posted by ynj
Note that A is multiplicative group,not a additive group...So a+A is not a coset..
i am not saying a+A is a coset ... but B is a coset .. and a+A happens to be the same as B

edit :: this is erroneous, proof corrected above. plz read a-A in place of a+A

14. oopps!!!

instead of taking a+A, plz take a-A, it all works out then. i am sorry for this confusion. i noticed this when i myself wrote what u were hinting. i will correct above too.

15. Originally Posted by nirax
see ...

it means there exist an element z^2 in A such that a + y^2 = z^2, but this is a contradiction to what we assumed about a.
ok....may be the statement of the question is unclear....I think the sum means +,not -.
I am not quite clear where is contradiction in your statement. a+y^2=z^2,a=z^2-y^2. if the sum actually means +, then z^2-y^2 is not a sum of two squares.......If the sum can mean -, then no problem exists.....

Page 1 of 2 12 Last

### finite field sum of two squares

Click on a term to search for related topics.