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

• First part is correct. For the second, try to prove that if you can represent $a$ and $b$ as a sum of two squares, then you can represent $ab$ as a sum of two squares, and find which primes you can represent as a sum of two squares. Then you are almost done. It remains to see that if you can represent $a$ as a sum of two squares, then you can represent each of its prime factors that appears with an odd exponent in $a$'s factorisation as a sum of two squares. – Daniel Fischer Nov 19 '13 at 20:10
• $ab=(m^2+n^2)(p^2+q^2)=(mp+nq)^2+(np-mq)^2$? - Aren't there infinitely many such primes? – user85798 Nov 19 '13 at 20:44
• Yes, there are infinitely many such primes. But there is a (rather simple) characterisation of these primes. – Daniel Fischer Nov 19 '13 at 20:45
• Is it that they're all $1\bmod 4$? – user85798 Nov 19 '13 at 21:17
• Well, and $2 = 1^2+1^2$. Can you prove that $p \not\equiv 3 \pmod{4}$ is necessary (I expect so) and sufficient (that's far less straightforward, no need to worry if you can't) for a prime $p$ to be representable as the sum of two squares? – Daniel Fischer Nov 19 '13 at 21:21

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

• Does this mean the answer is - all primes 1 mod 4 and any number with a prime factorisation containing only these primes? Or are there more? – user85798 Nov 20 '13 at 16:34
• It is NOT sufficient to find just the primes in $S$. Just because a number in $S$ can't be written as a product of two smaller numbers in $S$ does not mean that it cannot be written as product of two smaller numbers. – Aaron Nov 20 '13 at 16:43
• Sorry, I had been making an effort to avoid Gaussian arithmetic and botched that in the process. – Tim Ratigan Nov 20 '13 at 17:28