In this note, we are interested in the following well-known result:

Theorem: A prime $p \geq 3$ can be written as the sum of two squares if and only if $p \equiv 1 \ \mathrm{mod} \ 4$.

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 $p = 1 \ ( \mathrm{mod} \ 4)$ 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 $0$, $1$ or $2$ modulo $4$. Thus, because $p$ is necessarily odd, if it can be written as the sum of two squares then $p \equiv 1 \ \mathrm{mod} \ 4$.

Conversely, let $p$ be a prime satisfying $p \equiv 1 \ \mathrm{mod} \ 4$, and define the set

$S= \{ (x,y,z) \in \mathbb{N}^3 \mid x^2+4yz=p \}$.

Notice that $S$ is nonempty since $p \equiv 1 \ \mathrm{mod} \ 4$: there exists a $k \geq 1$ such that

$p=4k+1= 1^2+4 \cdot k \cdot 1$.

Now, let $f : S \to S$ be the map defined by

$(x,y,z) \mapsto \left\{ \begin{array}{cl} (x+2z, z, y-x-z) & \text{if} \ x 2y \end{array} \right.$

It is not difficult to show that $f$ is well-defined on $S$, because $(2y,y,z), (y-z,y,z) \notin S$ for all $y,z \geq 1$. Furthermore, an easy calculation proves that the image of $f$ is included into $S$.

Now, we want to prove that $f$ is an involution with exactly one fixed point.

The map $f$ is an involution. Let $(x,y,z) \in S$. If $x, then $x+2z>2z$ implies

$f \circ f(x,y,z)= (x+2z-2z, x+2z-z+y-x-z,z)=(x,y,z)$;

if $y-z, then $y-x+y-z< 2y-x<2y$ implies

$f \circ f(x,y,z)= (2y-2y+x,y, 2y-x-y+x-y+z)= (x,y,z)$;

if $x>2y$, then $x-2y implies

$f \circ f (x,y,z) = (x-2+2y, y , x-y+z-x+2y-y)=(x,y,z)$.

Therefore, $f \circ f = \mathrm{Id}_S$ ie. $f$ is an involution.

The map $f$ has only one fixed point. Clearly, if $p = 4k+1$ then $(1,1,k)$ is a fixed point of $f$. Conversely, let $(x,y,z) \in S$ be a fixed point of $f$. If $x < y-z$ then $(x,y,z)$ is a solution of

$\left\{ \begin{array}{l} x= x+2z \\ y= z \\ z = y- x -z \end{array} \right.$,

hence $x=y=z=0$, which is impossible. If $y-z then $(x,y,z)$ is a solution of

$\left\{ \begin{array}{l} x=2y-x \\ z = x-y+z \end{array} \right.$,

hence $x=y$. Thus, $(x,x,z) \in S$ implies $p=x^2+4xz=x(x+4z)$. Because $p$ is prime, necessarily $x=1$, and we deduce that $(x,y,z)= (1,1,k)$.

Finally, if $x >2y$ then $(x,y,z)$ is a solution of

$\left\{ \begin{array}{l} x =x -2y \\ y= x-y +z \\ z= y \end{array} \right.$,

hence $x=y=z=0$, which is impossible. Therefore, $f$ has exactly one fixed point: $(1,1,k)$.

In order to conclude the proof of our theorem, we need the following lemma:

Lemma: Let $X$ be a set and $h : X \to X$ an involution. Then $\# \mathrm{Fix}(h) \equiv \# X \ \mathrm{mod} \ 2$.

Proof. Let $Y$ be a maximal subset of $X$ satisfying $Y \cap h(Y)= \emptyset$. Then

$X= \mathrm{Fix}(h) \sqcup Y \sqcup h(Y)$,

which implies $\# X = \# \mathrm{Fix} (h) + 2 \cdot \# Y$. This proves the lemma. $\square$

Now we are able to conclude the proof of our theorem. Let $g : S \to S$ be a new map defined by $(x,y,z) \mapsto (x,z,y)$. Clearly, $g$ is a well-defined involution of $S$. By applying our previous lemma twice, we deduce that

$\# \mathrm{Fix}(g) \equiv \# X \equiv \# \mathrm{Fix} (f) \equiv 1 \ \mathrm{mod} \ 2$.

In particular, $\mathrm{Fix}(g)$ is nonempty. Let $(x,y,y) \in S$ be one of its points. Then

$p = x^2+4yy = x^2+(2y)^2$.

This proves that $p$ can be written as the sum of two squares, and the proof is complete.