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?
How do you prove that a prime is the sum of two squares iff it is congruent to 1 mod 4?
-
1Yes we figured that – 2010-07-23
-
7As long as you are open to accepting someone else's answer if it is better than your own :) – 2010-07-23
-
0For another interesting method of proof, see http://demonstrations.wolfram.com/Fermats4n1TheoremAndTheNQueensProblem/ 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.) – 2010-08-09
8 Answers
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$.
-
0"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? – 2010-07-24
-
2I 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. – 2010-07-24
-
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. – 2011-01-13
-
2@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. – 2012-08-22
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$.
-
2Dear 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.) – 2010-08-09
-
1Dear 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! – 2010-08-09
-
3Here'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. http://www.jstor.org/stable/2323912 – 2010-08-14
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$.
-
0I 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. – 2010-10-05
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.
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.
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}$.
-
8You should cite the source from where you copied this answer. – 2010-08-14
-
5@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.) – 2010-08-15
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.
-
0This is only proving the "only if" part of the sum-of-two-squares theorem as stated in the title of the question. – 2016-07-21
-
0see this list of proofs https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_des_deux_carr%C3%A9s_de_Fermat#D.C3.A9monstrations – 2016-07-21
-
0True, 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) – 2016-07-21
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.
-
0If 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? – 2016-07-21
-
0@pjs36 Apologies if this doesnt fit the correct criteria- I believe it is correct so long as I havent overlooked something major. – 2016-07-21
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.