Way back in 1640 Fermat stated that an odd prime number p can be written as the sum of two squares if and only if it has remainder 1 when divided by 4 (i.e p is of the form p = 4k+1 where k is an integer). It is believed that the first proof was given by Euler in 1747. Below are shown two of my favourite proofs in the “if” direction (the “only if” direction follows from any odd square being 1 modulo 4). Another cool proof worth looking at is by application of Minkowski’s Theorem for bounded symmetric convex sets .
In both proofs we use the fact that if p = 4k+1, then there exists an integer a such that . For example, we may choose , since
where the last step follows from Wilson’s theorem (in (p-1)! each element can be paired with its multiplicative inverse except for 1 and (p-1) – hence the product of the numbers from 1 to p-1 has remainder (p-1) modulo p).
Proof using Gaussian Integer Factorisation ():
In the set of Gaussian integers (), one can divide a number x by another y to obtain a quotient q and remainder r where |r| < |y|. This fact leads to unique factorisation being possible among the Gaussian integers (Euclidean domain implies unique factorisation via the principal ideal domain property.) Using the a found above, since is divisible by p and neither of its factors (a+i) nor (a-i) are multiples of p, p cannot be prime in the set of Gaussian integers. Hence we may write p = cd, where c and d are Gaussian integers each with norm greater than 1. This gives
which forces . Therefore if c = x+ iy we have
showing that p can be written as the sum of two squares.
Proof by Pigeonhole Principle ():
Using the a found above, consider the set of integers , where integers x and y satisfy . The number of possible pairs (x,y) is , and so applying the pigeonhole principle, there exist two distinct pairs and such that
Hence and . This means
Since the pairs and are distinct and ,
This forces and we are done.
Some more facts:
- A positive integer can be written as the sum of two squares if and only if any prime factor of the form 4k+3 occurs as an even power in its factorisation. To proves this requires the beautiful fact that if two numbers are each the sum of two squares, so too is their product:
- The number of ways in which the positive integer can be written as the sum of two squares (here have the form 4k+3, have the form 4k+1) is
where signs and order are distinguished (e.g. r(5) = 8). 
- We have the limit
This can be proved by counting the number of lattice points inside a circle of radius , then in the limit this number becomes the area of the circle. 
- Finally, if signs and order are not to be distinguished (e.g. 5 can be written as the sum of two squares in the one way ), the number of ways can be written as the sum of two squares is ()
, if all of the values are even,
(The first case deals with the possibility of whether n is of the form , in which case it has the additional representation .)
 N. Sato, Number Theory Olympiad notes, available at http://www.artofproblemsolving.com/Resources/Papers/SatoNT.pdf
 Weisstein, Eric W. “Sum of Squares Function.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/SumofSquaresFunction.html
 Sum of Two Squares Ways – Math Fun Facts
 I. Stewart and D. Tall, Algebraic Number Theory and Fermat’s Last Theorem, 3rd edition, 2002.