Venture a guess of what kind of odd primes can be written as

Venture a guess of what kind of odd primes can be written as a sum of two squares

Solution

If p = 4n + 1 then by Fermat\'s Little Theorem each of the numbers 1, 2⁴ⁿ , 3⁴ⁿ , ... , (4n)⁴ⁿ is congruent to one modulo p.

The differences 2⁴ⁿ - 1 , 3⁴ⁿ - 2⁴ⁿ , ... , (4n)⁴ⁿ - (4n - 1 )⁴ⁿ are therefore all divisible by p.

Each of these differences can be factored as a⁴ⁿ - b⁴ⁿ = (a²ⁿ - b²ⁿ)(a²ⁿ + b²ⁿ)

Since p is prime, it must divide one of the two factors. If in any of the 4 n 1 divides the first factor, then by the previous step we conclude that p is itself a sum of two squares (since a and b differ by 1 , they are relatively prime). So it is enough to show that p cannot always divide the second factor.

If it divides all 4n 1 differences 2²ⁿ - 1 , 3²ⁿ - 2²ⁿ , ... , (4n)²ⁿ - (4n - 1 )²ⁿ then it would divide all 4n 2 differences of successive terms, all 4n 3 differences of the differences, and so forth. Since the k th differences of the sequence

1^k , 2^k , 3^k , … are all equal to k! (Finite difference), the 2nth differences would all be constant and equal to (2n)!

which is certainly not divisible by p. Therefore, p cannot divide all the second factors which proves that p indeed the sum of two squares.

Thus every prime number of the form p = 4n + 1 is a sum of two squares.