When is an odd prime the sum of two squares?

gistfile1.txt

Claim:
Let p be an odd prime number. Then the following are equivalent:
 1. p is congruent to 1 modulo 4.
 2. There is some natural number m such that m^2 + 1 is a multiple of p.
 3. p is the sum of two squares.

Proof:
We'll prove (1) => (2) => (3) => (1).

(1) => (2):
Let p = 4k + 1, where k is a natural number.
By Fermat's little theorem, n^p = n (mod p), for every n < p.
Equivalently, n^(p-1) = 1 (mod p), and p-1 = 4k so p | n^4k - 1.
But n^4k - 1 = (n^2k + 1)(n^2k - 1), and p is prime,
so either p | (n^2k + 1) or p | (n^2k - 1).

So (2) holds, for some m = n^k, unless p | (n^2k - 1)
for every n < p. But the polynomial n^2k - 1 has at most
2k roots in the field Z_p, so this cannot be.

(2) => (3):
If p | (m^2 + 1), then in Z[i] we have p | (m + i)(m - i),
and clearly p divides neither (m + i) nor (m - i),
so p is not a prime in Z[i]. Therefore p can be factorised
in Z[i] (since Z[i] is a principal ideal domain, hence
not-a-prime implies not-irreducible). But p is prime in
Z, so it must factorise as (a + bi)(a - bi) for integers
a and b, hence be equal to a^2 + b^2.

(3) => (1):
The only squares in Z_4 are 0 and 1, so the sum of two squares
must be 0, 1, or 2. But the sum is odd, so it must be 1 (modulo 4).