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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Daniel Fischer Nov 19 '13 at 20:10
  • $\begingroup$ $ab=(m^2+n^2)(p^2+q^2)=(mp+nq)^2+(np-mq)^2$? - Aren't there infinitely many such primes? $\endgroup$ – user85798 Nov 19 '13 at 20:44
  • $\begingroup$ Yes, there are infinitely many such primes. But there is a (rather simple) characterisation of these primes. $\endgroup$ – Daniel Fischer Nov 19 '13 at 20:45
  • $\begingroup$ Is it that they're all $1\bmod 4$? $\endgroup$ – user85798 Nov 19 '13 at 21:17
  • $\begingroup$ 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? $\endgroup$ – 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}$.

  • $\begingroup$ 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? $\endgroup$ – user85798 Nov 20 '13 at 16:34
  • $\begingroup$ 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. $\endgroup$ – Aaron Nov 20 '13 at 16:43
  • $\begingroup$ Sorry, I had been making an effort to avoid Gaussian arithmetic and botched that in the process. $\endgroup$ – Tim Ratigan Nov 20 '13 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.