# 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
• 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

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

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

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

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

Let $$\Psi(n,m,k)=100n^2+20nm+m^2+4k^2$$

be a prime number for some $(n,m,k)$

Then:

This combination of $(n,m,k)$ must not share any factors. Except $(n,m)$ can share factors as long as: $$\gcd(n,m,k) = 1$$ So:

$$p = (10n+m)^2+(2k)^2$$

For the expression above to be a prime number, a combination of $(x,y)$ must be either even-odd or odd-even. But it already is for the $(n,m,k)$ we have picked.

If we pick n as some natural number, k as some positive natural number and m = 1,3,5,7,9 we fit the definition given above. Now we can expand and see that:

$$p = 100n^2+20nm+m^2+4k^2$$

This means $m^2\equiv1(mod4)$ since all other terms in the equation are already are congurent to $0(mod4)$.

But if you haven't already noticed for the choice for all of the m's we've picked all happen to be congurent to $1(mod4)$ when squared.

This means whether or not p is prime doesn't matter this equation will always produce a result of the form $p=4a+1$

Now this result may not give prime numbers all the time obviously. But our choice of $(n,m,k)$ was already for some, not all. Then one can state that:

If our choice of $(n,m,k)$ produces a prime number then it is a solution.

Except for the case $$1^2+1^2 = 2$$ which is the only case that will refute this, so it can be ignored.

Thus for:

$$p = x^2+y^2$$

if p is prime then:

$$p\equiv 1(mod4)$$

EDIT: The proof above isn't fully satisfactory since I start with $p=x^2+y^2$.

If we start backwards by assuming:

$$p \equiv 1(mod4)$$

Then

$$p = 4n+1$$

Now consider the following:

$$p=4n+1=100a^2+20ab+b^2+4c^2$$

If $10+b$ is odd then we don't have anything to worry about. So we have a look at $b^2$ and again $b = 1,3,5,7,9$ so:

$$b^2 \equiv 1(mod4)$$

or:

$$b^2 = 4m+1$$

Then we have:

$$p=4m+100a^2+20a(4m+1)+4c^2+1$$

So we have written $p$ as a sum of two squares:

$$p=(10a+4m+1)^2+(2c)^2$$

since one can say $x= 10a+4m+1$ and $y = 2c$.

So now I have shown that either way around the statement holds.

Infact this is related to Zagier's proof since if we let $y = c$ instead:

$$p=x^2+(2y)^2$$

Thus now we have shown if:

$$p \equiv 1(mod4)$$

then:

$$p = x^2+y^2$$

So now one can say that a prime number can be written as a sum of two squares iff $p \equiv 1(mod4)$

Also we know this is the only way besides the case $1^2+1^2=2$ to write primes as a sum of two squares because of the first argument where I said the combination of (x,y) must be even-odd or odd-even. And we know we can write ANY prime number of the form $4a+1$ as a sum of two squares because $\Psi(n,m,k)$ for the given limitations on $(n,m,k)$ can produce any odd natural number of the form $4a+1$. And since the set that represents all natural numbers of the form $4a+1$ includes the set of primes that can be written as $4a+1$.

Please let me know if there is any problems with the proof.

• This is only proving the "only if" part of the sum-of-two-squares theorem as stated in the title of the question. – Barry Cipra Jul 21 '16 at 15:41
• see this list of proofs fr.wikipedia.org/wiki/… – reuns Jul 21 '16 at 15:47
• True, yes but that is pretty much the whole problem, am I wrong? Because if you know the number you're given with is prime and can be written as a sum of two squares. Then it must be congurent to 1 (mod4) – guest4104 Jul 21 '16 at 15:50

I tried this via Wilson's theorem- It seems to work but would be grateful if someone could verify it/offer improvements?

Suppose a prime $p=1 \ \text{mod} 4$. By Wilson's theorem, $(p-1)! = -1 (\ \text{mod} p)$.

But $p-r = -r (\text{mod} p)$

So $-1= 1 (p-1) 2 (p-1)...( \frac{p-1}{2})( \frac{p-1}{2} ) = 1 (-1) 2(-2)...( \frac{p-1}{2})( \frac{p-1}{2} )= (-1)^{ \frac{p-1}{2}}(( \dfrac{p-1}{2})!)^{2} \ ( \text{mod} p)$

$(-1)^{ \frac{p-1}{2}}= (-1)^{ \frac{4k+1-1}{2}}=1$ so $-1 =( \dfrac{p-1}{2})!)^{2} \ ( \text{mod} p)$

In other words $np = 1 + (( \dfrac{p-1}{2})!)^{2}$ iff $p=1 \ \text{mod} 4$.

Any integer $x^{2} = 0,1 \ \text{mod} 4$ so we cant find an $x^2, y^2$ such that $x^2+y^2 = 3 \ \text{mod} 4$. As a prime is odd, it is either congruent to 1 or 3 mod 4 so it can only be written as a sum of 2 squares if congruent to 1 mod4.

• If you're not sure about the validity of your argument, and are looking for verification/improvement, have you considered posting this as a new question? – pjs36 Jul 21 '16 at 16:19
• @pjs36 Apologies if this doesnt fit the correct criteria- I believe it is correct so long as I havent overlooked something major. – Isomorphism Jul 21 '16 at 16:27

Let $$p \equiv 1\ (\text {mod}\ 4)$$ and $$a = \left (\frac {p-1} {2} \right )!$$. Observe that $$a^2 \equiv -1\ (\text {mod}\ p)$$ by Wilson's theorem. Consider an ideal $$I$$ of $$\Bbb Z[i]$$ such that $$I = \langle p,i-a \rangle$$. Observe that $$I \cap \Bbb Z = p \Bbb Z$$. Let $$R = \Bbb Z[i]/I$$. Then $$R$$ is a commutative ring with identity. Consider the map $$f : \Bbb Z \longrightarrow R$$ such that $$1 \mapsto 1_R$$, where $$1_R$$ is the multiplicative identity in $$R$$ and extend it to a homomorphism. Observe that $$f$$ is surjective and $$ker (f) = p \Bbb Z$$. So by the first isomorphism theorem we have $$\Bbb Z/p \Bbb Z \cong R$$. Since $$\Bbb Z[i]$$ is a PID $$\exists$$ $$a+ib \in \Bbb Z[i]$$ such that $$I = \langle a+ib \rangle$$. Observe that $$|R| = |\Bbb Z[i]/\langle a+ib \rangle| = a^2+b^2$$. So we have $$p = |\Bbb Z/p\Bbb Z| = a^2 + b^2,$$ as claimed.