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

Primes of the form $p=4k+1\;$ have a unique decomposition as sum of squares $p=a^2+b^2$ with $0<a<b\;$, due to Thue's Lemma.

Is it correct to say that, primes of the form $p=4n+3$, never have a decomposition into $2$ squares, because sum of the quadratic residues $a^2+b^2$ with $a,b\in \Bbb{N}$ $$ a^2 \bmod 4 +b^2 \bmod 4 \le 2? $$

If so, are there alternate ways to prove it?

share|cite|improve this question
I am not sure why you would want another way to prove it, as the mod 4 argument is so simple and water-tight - please explain. – Old John Jun 26 '12 at 21:50
@OldJohn it took me while to come to this proof. And I would to see this thing through different glasses. – draks ... Jun 26 '12 at 22:07
Your question is actually much easier to answer than the Thue lemma stuff you mention. – fretty Jun 26 '12 at 22:08
Yes - I can see that now from your new question - which looks interesting! – Old John Jun 26 '12 at 22:09
@fretty Go ahead! $ $ $ $, OldJohn thanks. – draks ... Jun 26 '12 at 22:09
up vote 6 down vote accepted

Yes, as it has been pointed out, if $a^2+b^2$ is odd, one of $a$ and $b$ must be even and the other odd. Then $$ (2m)^2+(2n+1)^2=(4m^2)+(4n^2+4n+1)=4(m^2+n^2+n)+1\equiv1\pmod{4} $$ Thus, it is impossible to have $a^2+b^2\equiv3\pmod{4}$.

In fact, suppose that a prime $p\equiv3\pmod{4}$ divides $a^2+b^2$. Since $p$ cannot be written as the sum of two squares, $p$ is also a prime over the Gaussian integers. Therefore, since $p\,|\,(a+ib)(a-ib)$, we must also have that $p\,|\,a+ib$ or $p\,|\,a-ib$, either of which implies that $p\,|\,a$ and $p\,|\,b$. Thus, the exponent of $p$ in the factorization of $a^2+b^2$ must be even.

Furthermore, each positive integer whose prime factorization contains each prime $\equiv3\pmod{4}$ to an even power is a sum of two squares.

Using the result about quadratic residues in this answer, for any prime $p\equiv1\pmod{4}$, we get that $-1$ is a quadratic residue $\bmod{p}$. That is, there is an $x$ so that $$ x^2+1\equiv0\pmod{p}\tag{1} $$ This means that $$ p\,|\,(x+i)(x-i)\tag{2} $$ since $p$ can divide neither $x+i$ nor $x-i$, $p$ is not a prime in the Gaussian integers, so it must be the product of two Gaussian primes (any more, and we could find a non-trivial factorization of $p$ over the integers). That is, we can write $$ p=(u+iv)(u-iv)=u^2+v^2\tag{3} $$ Note also that $$ 2=(1+i)(1-i)=1^2+1^2\tag{4} $$ Suppose $n$ is a positive integer whose prime factorization contains each prime $\equiv3\pmod{4}$ to even power. Each factor of $2$ and each prime factor $\equiv1\pmod{4}$ can be split into a pair of conjugate Gaussian primes. Each pair of prime factors $\equiv3\pmod{4}$ can be split evenly. Thus, we can split the factors into conjugate pairs: $$ n=(a+ib)(a-ib)=a^2+b^2\tag{5} $$ For example, $$ \begin{align} 90 &=2\cdot3^2\cdot5\\ &=(1+i)\cdot(1-i)\cdot3\cdot3\cdot(2+i)\cdot(2-i)\\ &=[(1+i)3(2+i)]\cdot[(1-i)3(2-i)]\\ &=(3+9i)(3-9i)\\ &=3^2+9^2 \end{align} $$ Thus, we have shown that a positive integer is the sum of two squares if and only if each prime $\equiv3\pmod{4}$ in its prime factorization occurs with even exponent.

share|cite|improve this answer

Yes. $a^2 \equiv -b^2 \ \ (p)$. Then raise to the $\frac{p-1}{2}$ power and use Fermat's little Theorem. You get $p|2$.

share|cite|improve this answer

Suppose $q$ is an odd sum of two squares. Then one square is even and one is odd. The odd square is, perforce, the square of an odd number and the even square is the square of an even number.

So we can write for some integers $m$ and $n$, $$q = (2m)^ 2 + (2n + 1)^2 = 4(m^2 + n^2 + n) + 1.$$ We conclude that $q \equiv 1 \mod 4.$

This very naive derivation shows that if $q$ is any odd integer with $q\not\equiv 1\mod 4$, $q$ cannot be the sum of two squares.

share|cite|improve this answer
Is this the "simple to prove the converse" as fretty stated above? How would your argument work here? – draks ... Jun 26 '12 at 22:30

Your Answer


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.