Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
    
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
6  
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$.

share|cite|improve this answer
    
"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
2  
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
3  
[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
1  
@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$.

share|cite|improve this answer
2  
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
1  
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
3  
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$.

share|cite|improve this answer
    
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.

share|cite|improve this answer

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}$.

share|cite|improve this answer
7  
You should cite the source from where you copied this answer. – Bill Dubuque Aug 14 '10 at 19:37
4  
@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.

share|cite|improve this answer
    
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 at 15:41
    
see this list of proofs fr.wikipedia.org/wiki/… – user1952009 Jul 21 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 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.

share|cite|improve this answer
    
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 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. – Robert C Jul 21 at 16:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.