A
complex number a+bi is a Gaussian
integer iff
a and
b are both integers. The collection of all
Gaussian integers is normally denoted by
Z[i].
This is a
subring of
C.
We are going to use the properties of the Gaussian integers
to prove a result of Euler. This result is about the usual integers
(the Gaussian integers are used in the proof but not
in the statement).
Theorem Let p be an odd prime number.
Then p is congruent to 1 mod 4 iff
p can be written as a^{2}+b^{2},
for some integers a,b. Further, this expression as a sum of two squares
is essentially
unique.
A couple of remarks about the theorem
 This theorem was first stated by Fermat in a letter to Mersenne
but he didn't offer any proof. Pesky margins!

Saying that the expression is essentially unique means that
any similar expression arises from the given one by sign changes of a
and b or by swapping a and b.
Before we can prove this we need to find out some more
about the Gaussian integers.
Lemma 1. The ring of Gaussian integers
Z[i] is a unique factorization domain
For a proof see the UFD writeup.
Define a norm function on the Gaussian integers
by d(a+bi)=a^{2}+b^{2} (the square of the modulus).
Note that this norm is always a nonnegative integer and that
d(xy)=d(x)d(y), for two Gaussian integers x,y.
Lemma 2

For a Gaussian integer u we have that u is a unit
iff and only if d(u)=1.

The multiplicative group of the Gaussian integers is {1,1,i,i}
(which is cyclic of order 4).
Proof
if u is a unit then uu^{1}=1. Thus
1=d(1)=d(uu^{1})=d(u)d(u^{1}). It follows that
d(u)=1.
Write u=a+bi, for integers a,b.
If d(u)=1 then a^{2}+b^{2}=1. Thus
one of a or b must be 1 or 1 and the other one must
be zero. This gives that the u with d(u)=1
are {1,1,i,i}. These are all units. This completes the proof
of the lemma.
Lemma 3. Let u be a Gaussian integer. If d(u) is a prime
number then u is a prime Gaussian integer.
Proof
We have to show that u is irreducible. If
u=ab for a,b nonunits then d(u)=d(a)d(b). Since
d(u) is a prime number, p say it must be that
d(a)=p and d(b)=1 (or vice versa). But This is impossible,
by Lemma 2, since b is assumed not to be a unit. This contradiction
shows that u is irreducible and hence prime.
Let's prove the ==> direction of Euler's result. Suppose that p is an odd prime
and suppose that p is congruent
to 1 mod 4 (i.e. p1 is divisible by 4).
Lemma 4
There is
an integer c with c^{2} congruent to 1 mod p.
Proof There is an element of order 4 in the multiplicative group
of the finite field
Z_{p} (the ring of integers mod p) for
this group is cyclic (see the finite field writeup) and it's
order is divisible by 4, by the assumption on p. Let
t be this element. Then t^{2} has
order 2. Now the polynomial x^{2}1 has roots 1 and 1 in
Z_{p}.
Since a polynomial of degree 2 has at most two roots this
tells us that 1 is the only element in the multiplicative group
of Z_{p} with order 2, so it must be that
t^{2}=1. Letting c be an integer whose
class mod p is t gives the result.
Back to ==> direction of Euler's result.
We have p divides 1+c^{2},
in Z by Lemma 4. This means that it also divides it in
Z[i]. But now we can factorize
1+c^{2}=(1+ci)(1ci). So this means that p is not
a prime element of Z[i] for we can't have
p(1+ci) or (1ci). For, if p(x+yi)=1+ci for some
integers x,y then equating real and imaginary parts we see that
px=1 which is clearly impossible.
Since p is not prime in Z[i] it is not irreducible
either. Thus we can write it p=(a+bi)(u+vi) as a product of
nonunits in Z[i]. Taking d
of both sides we get that p^{2}=
(a^{2}+b^{2})(u^{2}+v^{2}). Since p
is a prime number, the fundamental theorem of arithmetic tells us
that either d(a+bi) and d(u+vi) both equal p
or that one of them has norm 1. Since, neither is a unit, by assumption,
the first possibility must occur (by Lemma 2)
and p=d(a+ib)=a^{2}+b^{2}, is expressed as a sum of
squares, as required.
Now for the uniqueness.
Suppose that p=a^{2}+b^{2}=e^{2}+f^{2}.
The argument at the end of the last paragraph shows that we have
d(a+ib)=d(aib)=d(e+if)=d(eif)=p. It follows
from Lemma 3 that
a+ib,aib,e+if,eif are all prime Gaussian integers.
Now by Lemma 1, since we have (a+ib)(aib)=(e+ib)(eib) uniqueness
of factorisation says that either a+ib=(e+ib)u,
or a+ib=(eib)u, for some unit u. By Lemma 2, u is one
of 1,1,i,i. Substituting in these values we see that the difference
between a,b and e,f is just given by sign changes or
swapping,as is required.
Finally we prove the converse. Suppose that p=a^{2}+a^{2}.
Since p is odd it must be that one of a and b
is odd and the other
is even. The square of an even integer is congruent to zero mod 4
and the square of an odd integer is congruent to 1 mod 4, hence the result.