Sum of squares using Gaussian integers Using Gaussian integers $a+ib$ ($a,b\in\mathbb{Z}$), one can prove that a prime $p\in\mathbb{Z}$  is sum of two squares in $\mathbb{Z}$ if and only if $p\equiv 1\pmod 4$.
Question: Using Gaussian integers, is there any result which says about what integers can be expressed as sum of two (non-zero) squares in $\mathbb{Z}$? 
I do not know how factorization of $m\in\mathbb{Z}$ into product of primes will help for this, since 


*

*$2$ is sum of two squares, but the product $2.2$ is not.

*$4$ is not sum of two squares, $2$ is sum of two squares, but $4.2$ is sum of two squares. 
 A: Your definition of "$0$ is not a square" is confusing you. With this problem, it turns out to be much easier to allow $0$ to be a square. You can then introduce your "$0$ is not a square" condition at the end. A number is a sum of two non-zero squares if (a) it is a sum of two squares and (b) it is not itself a square.
Once you have allowed yourself to think like this, the answer will probably become clear to you. A sketch goes something like this.


*

*Let us deal with square-free $n$ only, because every number $N$ can be expressed as $N=k^2n$, where $k\ge{0}$ is an integer and $n\ge{1}$ has no repeated prime factors. Your "two non-zero squares" condition amounts to insisting that $n>1$.

*If $n$ is a product of primes which equal 1 modulo 4, it is a product of norms of Gaussian integers and therefore the norm of a product of Gaussian integers and therefore the norm of a Gaussian integer and therefore the sum of two squares.

*If $n$ has prime factors which equal 3 modulo 4, it has prime factors which are not norms of Gaussian integers. Could the product of such prime factors be the norm of a Gaussian integer? No. For example, if $3\times{7}$ were the norm of a Gaussian integer, then it would be factorisable as $(a+bi)(a-bi)$ and also as $3\times{7}$. But the Gaussian integers are a unique factorisation domain, so this is impossible.
Hence a necessary and sufficient condition for square-free $n$ to be expressible as a sum of squares is that it should have no prime factors which equal 3 modulo 4.
When you are putting back the squares, translating from $n$ language to $N$ language, you will see that your "sum of non-zero squares" condition is equivalent to "$n\ge{1}$".
A: Assume that the prime factorization of a natural number $n$ is
$$
n=2^a\prod_{i, p_i\equiv-1\pmod4}p_i^{s_i}\prod_{j,p_j\equiv1\pmod4}p_j^{r_j}.\qquad(*)
$$
We need the multiplicativity of the norm $N(u+vi)=(u+vi)(u-vi)=u^2+v^2$ and the known splitting behavior of rational primes in $\Bbb{Z}[i]$. Namely:


*

*$2$ ramifies and is up to a unit factor equal to $(1+i)^2=2i$, where $1+i$ is a prime of $\Bbb{Z}[i]$.

*If $p\equiv-1\pmod4$, then $p$ is also a prime of $\Bbb{Z}[i]$.

*If $p\equiv1\pmod4$, then $p$ factors as $p=(a+bi)(a-bi)$ for some two primes $a\pm bi$ of $\Bbb{Z}[i]$. Here $ab\neq0$.


Let's look at the three factors on the r.h.s. of $(*)$, call them $n_1,n_2,n_3$, individually.


*

*If $n_1=2^a$ and $n=u^2+v^2$, then $N(u+vi)=2^a$. Unique factorization in $\Bbb{Z}[i]$ implies that $u+vi=i^k(1+i)^a$. We easily see that if $a$ is even, then either $u=0$ or $v=0$. But if $a$ is odd, then $|u|=|v|$. The conclusion is that $2^a$ is always a sum of two squares, but a sum of two non-zero squares iff $a$ is odd.

*If $n_2=\prod_{i, p_i\equiv-1\pmod4}p_i^{s_i}$ it is well known that $n_2$ is a sum of two squares iff it is a square (i.e. if all the exponents $s_i$ are even). Furthermore, $n_2$ cannot be a sum of two non-zero squares in this case.

*If $n_3=\prod_{j,p_j\equiv1\pmod4}p_j^{r_j}$. Then each of the primes $p_j$
is a sum of two squares: $p_j=(a_j+ib_j)(a_j-ib_j)=a_j^2+b_j^2$, $a_jb_j\neq0$. Consider the product
$$u+iv=\prod_j(a_j+ib_j)^{r_j}.$$
I claim that if $n_3>$ both $u$ and $v$ are non-zero. This follows from the UFD-property. For if $uv=0$ then $u+iv$ and $u-iv$ are associates in $\Bbb{Z}[i]$, i.e. their ratio is a power of $i$. But,
$u-iv=\prod_j(a_j-ib_j)^{r_j}$, and for all $j$ the primes $a_j+ib_j$ are $a_j-ib_j$ are non-associates, so $uv=0, n_3>1$ violates uniqueness of factorization of the Gaussian integer $u+iv$. The conclusion is that if $n_3>1$ it is a sum of two non-zero integers.


We need to put these pieces together. Fermat's theorem (see the above link, but we actually got that as a by-product) states that $n$ is a sum of two squares, iff $n_2$ is a square. I claim that

$n$ is a sum of two non-zero squares, iff $n_2$ is a square and either $n_1$ or $n_3$ is a sum of two non-zero squares.

If $n_1$ or $n_3$ (or both) is a sum of two non-zero squares, then using the multiplicativity of the norm gives rise to a presentation of $n$ as a sum of two non-zero squares. If $n_1=N(a_1+ib_1)$, $n_2=a_2^2$ and $n_3=N(a_3+ib_3)$, then then product $u+iv=(a_1+ib_1)a_2(a_3+ib_3)$ cannot be real or pure imaginary by the argument from item 3 above, and $N(u+iv)=n$.
OTOH, if $n=N(u+iv)$ with $uv\neq0$, then the prime factorization of $u+iv$ must either contain a factor of $n_3>1$ or an odd power of $(1+i)$.

Summary: $n$ is a sum of two non-zero squares, iff all the exponents $s_i$ are even, and in addition either $a$ is odd, or at least one of the exponents $r_j>0$.

