In this note, we are interested in the following well-known result:
Theorem: A prime can be written as the sum of two squares if and only if .
There exist many different proofs of this theorem, but a surprising one is exposed by D. Zagier in his article A one-sentence proof that every prime is a sum of two squares. Our note is dedicated to this proof.
First of all, it is easy to prove that the sum of two squares is either congruent to , or modulo . Thus, because is necessarily odd, if it can be written as the sum of two squares then .
Conversely, let be a prime satisfying , and define the set
Notice that is nonempty since : there exists a such that
Now, let be the map defined by
It is not difficult to show that is well-defined on , because for all . Furthermore, an easy calculation proves that the image of is included into .
Now, we want to prove that is an involution with exactly one fixed point.
The map is an involution. Let . If , then implies
if , then implies
if , then implies
Therefore, ie. is an involution.
The map has only one fixed point. Clearly, if then is a fixed point of . Conversely, let be a fixed point of . If then is a solution of
hence , which is impossible. If then is a solution of
hence . Thus, implies . Because is prime, necessarily , and we deduce that .
Finally, if then is a solution of
hence , which is impossible. Therefore, has exactly one fixed point: .
In order to conclude the proof of our theorem, we need the following lemma:
Lemma: Let be a set and an involution. Then .
Proof. Let be a maximal subset of satisfying . Then
which implies . This proves the lemma.
Now we are able to conclude the proof of our theorem. Let be a new map defined by . Clearly, is a well-defined involution of . By applying our previous lemma twice, we deduce that
In particular, is nonempty. Let be one of its points. Then
This proves that can be written as the sum of two squares, and the proof is complete.