How do you prove that a prime is the sum of two squares iff it is congruent to 1 mod 4?

It is a theorem in elementary number theory that if $p$ is a prime and congruent to 1 mod 4, then it is the sum of two squares. Apparently there is a trick involving arithmetic in the gaussian integers that lets you prove this quickly. Can anyone explain it?

-
Yes we figured that –  BlueRaja - Danny Pflughoeft Jul 23 '10 at 17:27
@Akhil: It is acceptable to answer your own question. –  John Gietzen Jul 23 '10 at 17:34
As long as you are open to accepting someone else's answer if it is better than your own :) –  Larry Wang Jul 23 '10 at 18:06
For another interesting method of proof, see demonstrations.wolfram.com/… and the Larson article it refers to. (L. C. Larson, "A Theorem about Primes Proved on a Chessboard," Mathematics Magazine, 50(2), 1977 pp. 69–74.) –  Doug Chatham Aug 9 '10 at 19:02

Let $p$ be a prime congruent to 1 mod 4. Then to write $p = x^2 + y^2$ for $x,y$ integers is the same as writing $p = (x+iy)(x-iy) = N(x+iy)$ for $N$ the norm.

It is well-known that the ring of Gaussian integers $\mathbb{Z}[i]$ is a principal ideal domain, even a euclidean domain. Now I claim that $p$ is not prime in $\mathbb{Z}[i]$. To determine how a prime $p$ of $\mathbb{Z}$ splits in $\mathbb{Z}[i]$ is equivalent to determining how the polynomial $X^2+1$ splits modulo $p$.

First off, $-1$ is a quadratic residue modulo $p$ because $p \equiv 1 \mod 4$. Consequently, there is $t \in \mathbb{Z}$ with $t^2 \equiv -1 \mod p$, so $X^2+1$ splits modulo $p$, and $p$ does not remain prime in $\mathbb{Z}[i]$. (Another way of seeing this is to note that if $p$ remained prime, then we'd have $p \mid (t+i)(t-i)$, which means that $p \mid t+i$ or $t \mid t-i$.)

Anyway, as a result there is a non-unit $x+iy$ of $\mathbb{Z}[i]$ that properly divides $p$. This means that the norms properly divide as well. In particular, $N(x+iy) = x^2+y^2$ properly divides $p^2$, so is $p$ or $1$. It cannot be the latter since otherwise $x+iy$ would be a unit. So $x^2+y^2 = p$.

-
"To determine how a prime $p$ of $\mathbb{Z}$ splits in $\mathbb{Z}[i]$ is equivalent to determining how the polynomial $X^2+1$ splits modulo $p$" - What theorem is that? –  Casebash Jul 24 '10 at 0:08
I don't think it has a name, but basically the point is that determing how $p$ splits in $\mathbb{Z}[i] = \mathbb{Z}[X]/(X^2+1)$ is the same thing as considering the quotient by the ideal generated by $p$, i.e. $\mathbb{Z}_p[X]/(X^2+1)$. If $X^2+1$ splits modulo $p$, then this ring has two prime ideals. So essentially it reduces to properties of quotient rings. –  Akhil Mathew Jul 24 '10 at 0:29
[Originally left as a reply when I didn't have enough reputation]: Sorry that I don't have enough rep yet, I just want to point out the fact Casebash's asking about in Akhil's comment goes by the name Kummer-Dedekind theorem. –  Soarer Jan 13 '11 at 6:44
@Casebash: The essential point for the argument for the equivalence is that the ring $Q=\mathbb Z[X]/(p,X^2+1)$ can be viewed as a quotient ring of a Euclidean (and therefore principal) domain in two ways; saying that $Q$ is not a field (or equivalently not a domain) has repercussions, namely the generator of an ideal being reducible, in both those Euclidean domains, which repercussions are then of course equivalent. I don't think this requires the Kummer-Dedekind theorem. –  Marc van Leeuwen Aug 22 '12 at 9:56

Here is another proof without complex numbers.

We start with proving that there exists $z \in \mathbb{N}$ such that $z^2 + 1 \equiv 0 \pmod p$. We do this in the same way as Akhil Mathew.

Let we have $a^2 + b^2 = pm$. Take $x$ and $y$ such that
$x \equiv a \pmod m$ and
$y \equiv b \pmod m$ and
$x, y \in [-m/2, m/2)$.

Consider $u = ax + by$ and $v = ay - bx$. Then $u^2 + v^2 = (a^2 + b^2)(x^2 + y^2)$. Moreover, $u$ and $v$ are multiples of $m$. Hence $(u/m)^2 + (v/m)^2 = p (x^2 + y^2)/m$. $(x^2 + y^2)/m$ is an integer because of the definition of $x$ and $y$ and that $a^2 + b^2 = pm$.
Also $(x^2 + y^2)/m$ is less than $m/2$.

Now we change $a$ by $u$ and $b$ by $v$ and continue this process until we get $m=1$.

Notice that this is quite efficient way to find representation of $p$ as a sum of two squares - it takes $O(\log p)$ steps to find it provided we have found $z$ such that $z^2 + 1$ is multiple of $p$.

-
I don't understand your proof, could you please give me a pointer? I don't see the connection with the mentioned $z$, and I fail to see what the new $m$ is at the end of the algorithm's first step. –  Weltschmerz Oct 5 '10 at 20:23

Taken From I.N. Herstein There are 2 results which i am going to use.

1. Let $p$ be a prime integer and suppose that for some integer $c$ relatively prime to $p$ we can find integers $x$ and $y$ such that $x^{2}+y^{2}=cp$. Then $p$ can be written as the sum of 2 squares.

2. If $p$ is a prime of the form $4n+1$, then we can solve the congruence $x^{2} \equiv \ -1 \ (mod) \ p$.

Now the main result. If $p$ is a prime of the form $4n+1$ then $p$ is the sum of 2 squares.

Proof. By 2 there exists and $x$ such that $x^{2} \equiv -1 \text{mod} \ p$. So $x$ can be chose such that $0 \leq x \leq (p-1)$. We can restrict the size of $p$ even further, namely to satisfy $|x| \leq \frac{p}{2}$. For if $x > p/2$ then, $y=p-x$ satisfies $y^{2} \equiv -1 \text{mod} \ p$ but $|y| \leq p/2$. Thus we may assume that we have an integer $x$ such that $|x| \leq p/2$ and $x^{2}+1$ is a multiple of $p$ say $cp$. Now $cp=x^{2}+1 \leq p^{2}/4 +1 < p^{2}$, hence $c < p$ and hence $(c,p)=1$. Invoking (1) we have $p=a^{2}+b^{2}$.

-
You should cite the source from where you copied this answer. –  Bill Dubuque Aug 14 '10 at 19:37
@Chandru1: Thanks for adding the reference! Please do add references like this whenever you take something from somewhere. (It is indeed the proof from I. N. Herstein's Topics in Algebra, Theorem 3.G.) –  ShreevatsaR Aug 15 '10 at 19:00

Perhaps my favorite argument (other than any arguably "correct" arguments, such as the one Akhil has given, or arguments starting from the fact that $x^2 + y^2$ is the unique binary quadratic form of discriminant $-4$ up to equivalence) uses continued fractions. Suppose that $u^2 \equiv -1 \pmod{p}$, and consider the continued fraction expansion of the rational number $u/p$. Let $r/s$ be the last convergent to $u/p$ with the property that $s < \sqrt{p}$. Then, setting $x=s$ and $y = rp-us$, one has $x^2 + y^2 = p$.

Here's the argument: let $r'/s'$ be the convergent following $r/s$. Then the basic theory of continued fractions gives the estimate $|r/s - u/p| < 1/ss'$, and the right-hand side is less than $1/s\sqrt{p}$ by hypothesis. Clearing denominators gives $y < \sqrt{p}$, so that $0 < x^2 + y^2 < 2p$. On the other hand $x^2 + y^2$ is checked to be divisible by $p$ (by choice of $u$), so must be equal to $p$.

-
Dear Dave, This is very nice. In fact, it must be very close to (essentially the same as?) both the proof the $\mathbb Z[i]$ is a Euclidean domain, and the reduction theory argument showing uniqueness of $x^2 + y^2$. In other words, it probably qualifies as a "correct" argument in its own right. (But perhaps lacking the surrounding theoretical infrastructure that those arguments admit, which I guess is what you are getting at with your parenthetical remark.) –  Matt E Aug 9 '10 at 16:21
Dear Matt: yes, I agree. The content is there, but (it seems to me) it's hard to see that it's there unless one already knows another argument in some more theoretical context! –  D. Savitt Aug 9 '10 at 16:36
Here's a convenient reference for this: Editor's Corner: The Euclidean Algorithm Strikes Again, Stan Wagon, Amer. Math. Monthly, Vol. 97, No. 2 (Feb., 1990), pp. 125-129. jstor.org/stable/2323912 –  Bill Dubuque Aug 14 '10 at 19:40

There is an amazing proof of this due to Don Zagier : one-sentence proof.

-