Which sets of integers can be expressed in the form $m^2 + n^2$ and $m^2 - n^2$ where $m$ and $n$ are integers? I'm trying to find which sets of integers can be expressed in the form 
$\mathrm{1})\,\,m^2 - n^2$ and, 
$\mathrm{2)}\,\,m^2 + n^2$
where $m$ and $n$ are integers.
For the first part I expressed it as $(m-n)(m+n)$ and figured that the only numbers that cannot be expressed in this form are numbers of the form $2(2n-1) = 4n - 2\quad n\in\mathbb{Z}$. 
Is this correct?
I'm not sure how to start the second part.
 A: As you mentioned, $(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2$, so the set $S=\{a^2+b^2\mid a,b,\in\mathbb{Z}\}$ is closed under multiplication.  Thus, the first step is to find all primes $p\in S$.  First of all, it is clear $2=1^2+1^2\in S$.  Additionally, the only quadratic residues $\pmod{4}$ are $0$ and $1$, so $a^2+b^2$ can only be $0,1$, or $2$ $\pmod{4}$ (i.e. not $3$).  So it is clear that all primes that are a sum of two squares is a subset of  $2$ and primes $p\equiv1\pmod{4}$.  It turns such primes are exactly this set, but the proof all primes of the form $4k+1$ for $k\in\mathbb{N}$ are elements of $S$ uses a lot of number theory.  My favorite one is the one below, which uses something called Minkowski's Theorem.
Minkowski's Theorem states that if you have an area  $K$ on a lattice with a fundamental parallelogram of size $\Delta$, $K$ is symmetric about the origin (i.e. $-f(x)=f(-x)$), $K$ is convex (for any points $\vec p$ and $\vec q$ in $K$, all points between $\vec p$ and $\vec q$ must also be in $K$), and $K>4\Delta$, then there must exist at least $1$ lattice point in $K$ other than the origin.
The proof is as follows: Consider cutting up $K$ into parallelograms of size $4\Delta$ that are, in essence $2\times2$ lattices, starting with the 4 fundamental parallelograms around $\vec 0$.  Then, translate each of these areas so that their center lies at the origin. Having translated all of $K$ into an area of size $4\Delta$, by the pigeonhole principle, there must be a point of overlap.  Let $\vec p$ be one of the overlapping points such that $\vec p+2m\vec v+2n\vec w\in K$, where $\{\vec v,\vec w\}$ generate the lattice and $m,n\in\mathbb{Z},\ (m,n)\neq(0,0)$ .  Since  $K$ is symmetric about the origin, $-\vec p\in K$.  Finally, since $K$ is convex, the midpoint of $-\vec p$ and $\vec p+2m\vec v+2n\vec w$ is in $K$.  Therefore $m\vec v+n\vec w\in K$ and is a lattice point that is not the origin.
Consider the group $\mathbb{Z}/p\mathbb{Z}=\{1,2,\ldots,p-1\}$ under multiplication ($p$ prime).  Note that, thanks to Fermat's Little Theorem, $n^{p-1}\equiv 1\pmod{p}$ for all $n\in\mathbb{Z}/p\mathbb{Z}$.  If $n$ is a quadratic residue (QR), that is if there exists $a\in\mathbb{Z}/p\mathbb{Z}$ such that $a^2\equiv n\pmod{p}$, then $1\equiv a^{p-1}\equiv n^{\frac{p-1}{2}}\pmod{p}$.  Since $$a^{p-1}-1=(a^{\frac{p-1}{2}}-1)(a^\frac{p-1}{2}+1)\equiv 0\pmod{p}$$
We know that $a^\frac{p-1}{2}+1$ and $a^{p-1}{2}-1$ must have $p-1$ roots between them.  We already know that $a^\frac{p-1}{2}-1$ has $\frac{p-1}{2}$ roots, and Lagrange's theorem says that there can be no more roots than the degree of the polynomial.  Therefore all remaining $\frac{p-1}{2}$ elements must satisfy $a^{\frac{p-1}{2}}\equiv -1\pmod{p}$.  Thus we obtain Euler's Criterion:  
$$n\in\mathbb{Z}/p\mathbb{Z}\mathrm{\ is\ a\ QR} \iff\ n^{\frac{p-1}{2}}\equiv 1\pmod{p}$$
$(-1)^\frac{p-1}{2}\equiv 1\iff2|\frac{p-1}{2}\iff p\equiv 1\pmod{4}$ therefore there exists $n\in\mathbb{Z}/p\mathbb{Z}$ such that $n^2+1\equiv 0\pmod{p}$ iff $p\equiv 1\pmod{4}$. Now, given such an $n$, let's create a lattice!
Consider the lattice generated by $\{\vec v=\langle n,1\rangle,\vec w=\langle 0,p\rangle\}$  Note that for any $(p_1,p_2)$ on this lattice, $p_1^2+p_2^2=(k\cdot n+\ell\cdot 0)^2+(k\cdot 1+\ell\cdot p)^2\equiv k^2(n^2+1)\equiv 0 \pmod{p}$.  Furthermore, the area of the fundamental parallelogram is $\begin{array}{|cc|}n&1\\0&p\end{array}=n\cdot p<p^2$.  If we consider the area $K=\{(x,y)\mid x^2+y^2<2p\}$, then $|K|=\pi(2p)^2=4\pi p^2>4p^2>4np$.  Since $K$ is a circle, it is symmetric about the origin.
Therefore, $K$ satisfies all criteria for Minkowski's Theorem and contains a lattice point.  This lattice point satisfies $p|x^2+y^2$ and $x^2+y^2<2p$, so $x^2+y^2=p$.
After finding all primes in $S$, we need to find all composite numbers in $S$ with factors not in $S$.  Let $p\equiv 3\pmod{4}$.  If $p|a^2+b^2$, then $p|(a+bi)(a-bi)$.  Assume there exist $\alpha,\beta\in\mathbb{Z}[i]$ such that $\alpha\beta=p$.  Then $N(\alpha)N(\beta)=N(p)=p^2$.  $N(\alpha),N(\beta)\neq p$ since $p$ cannot be written as a sum of two squares, so at least one of $\alpha, \beta$ is a unit and $p$ is "prime" in $\mathbb{Z}[i]$.  Thus $p|a+bi$ and $p|a-bi$, so $p|a$ and $p|b$.  Therefore the only factors left unaccounted for are $p^2$ for all $p\equiv 3 \pmod{4}$.
