True or false: An integer prime p can be written as a sum of two squares if and only if ...?

Question

True or false:

An integer prime p can be written as the sum of two squares if and only if there exists an integer n such that n^2 is congruent to -1 (modulo p).

Prove your answer in a fairly elementary way.

I'm not sure I understood that infinite-regress proof, actually.

Answer 1

It's true.

Consider first n^2 + 1 = k.p where n > k > 1

Let n = i.k + m

Prove that m^2 + 1 = k.j where j < k

Then prove that you can cancel out k^2 from

(n^2 + 1)(m^2 + 1) = j.k^2.p

to leave r^2 + s^2 = j.p . . . and if j > 1, you can reduce both r and s modulo j to construct t^2 + u^2 = j.h where h < j, and multiply out to cancel j^2 . . . so you can keep going, and the only thing that can stop you is x^2 + y^2 = L.n when L = 1.

For the other way round, start with a^2 + b^2 = p, and multiply by c^2 chosen so that b.c = k.p + 1.

Elementary number theory is FUN!

Answer 2

what?