Can someone give me a hint for how to show if then ?
Thanks a lot!
Additional problem: Prove that if and where are odd and are even and then . In other words, we have a certain level of uniqueness in the decomposition of into sum of squares.
Here is a very elementary way of proving this result. Remember if then there is so that . There is an elementary way of showing this too, just let and use Wilson's theorem. But whatever, we will accept this result.
We need a Lemma first: let then there exists with so that .
To prove this let . And define . The set has at most different values. Since and there are only two residue classes of mod it means there are so that and or (by pigeonhole principle). If then by considering this congruence it would mean , which is a contradiction. Similarly if then it would force , which is a contradiction. Therefore, . Thus, we have . Set and we see that . Remember that , thus must be equal to .
Now we can prove that is a sum of two squares. Let be a square root of mod i.e. in less fancy language . Pick integers so that and . Therefore, . Thus, for some . We will complete the proof if we can show .