# $p=4n+3$ never has a Decomposition into $2$ Squares, right?

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?

• 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

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.

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

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.

• 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