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<y-z \\ (2y-x, y, x-y+z) & \text{if} \ y-z< x < 2y \\ (x-2y, x-y+z, y) & \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<y-z, 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<x<2y, 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<x-y+z-y 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<x< 2y 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.