More Sums of Squares

Age 16 to 18
Article by Tom Sanders

Published January 1999,February 2011.


One of the earlier NRICH articles Sums of Squares and Sums of Cubes has spurred me into further thought which I would like to share with the NRICH members. I would like to put forward some work I have done on the representation of numbers as sums of squares, and pose some further questions.

Consider some number $m$ such that: $$m = x^2 + y^2 + z^2.$$ The purpose of the following argument is to determine the form which $m$ can take such that it can be written as the sum of three squares. We shall begin by considering the situation where $4^\alpha$ divides $m$ such that $\alpha$ is a positive integer. If we consider $x$, $y$ and $z$ to be interchangeable then there are four different selections of $x$, $y$ and $z$ being odd or even, and these give the following situation. \begin{eqnarray} \mbox{3 odd numbers}: &x^2+y^2+z^2 \equiv 3 &\pmod 4\\ \mbox{2 odd numbers}: &x^2+y^2+z^2 \equiv 2 &\pmod 4\\ \mbox{1 odd number}: &x^2+y^2+z^2 \equiv 1 &\pmod 4\\ \mbox{0 odd numbers}: &x^2+y^2+z^2 \equiv 0 &\pmod 4\\ \end{eqnarray}
Hence if 4 divides $m$, we have all of $x$, $y$ and $z$ even and we can therefore divide $m$ by 4 and each of $x$, $y$ and $z$ by 2. We continue this procedure until not all of $x$, $y$ and $z$ are even.

Theorem 1:

The congruence $x^2\equiv-1\pmod {p}$, where $p$ is a prime, has a solution $x$ if and only if $p\equiv 1\pmod {4}$ or $p=2$.

Proof:

If $p=2$ then we can see the solution $x=1$ and our work is finished, so we assume that $p> 2$. Now take the congruence and raise both sides to the power $(p-1)/2$, hence we have: $$(-1)^{p-1\over2} \equiv \left(x^2\right)^{p-1\over2} \equiv x^{p-1} \pmod p$$ However, we know by Fermat's Little Theorem that $$x^{p-1}\equiv 1\pmod p \,\Rightarrow \, (-1)^{p-1\over2}\pmod p$$ However, since $p> 2$ we have $$-1 \neq 1\pmod p$$ which in turn means that $(p-1)/2$ is even, or more exactly that $p$ is $1\pmod 4$, as required. So we have proved that the congruence has a solution only if $p\equiv 1\pmod 4$. It is true, but harder to prove, that it has a solution if $p\equiv 1\pmod 4$. I shan't do that here.

Theorem 2:

The congruence $x^2\equiv-2\pmod p$, where $p$ is a prime, has a solution $x$ if and only if $p=2$ or $p\equiv 1\pmod 8$ or $p\equiv 3\pmod 8$.

Proof:

We begin with a similar tack with our application of Fermat's Little Theorem, which initially produces the following congruence which needs to be solved: $$(-2)^{p-1\over2} \equiv 2^{p-1\over2}(-1)^{p-1\over2}\equiv 1\pmod p$$ We observe that $p=2$ is a solution and now assume $p> 2$. The next step is to show that the following identity is true: $$2^{p-1\over 2}\equiv(-1)^{p+1\over4}\pmod p$$ Consider the least positive residues of the integers $2,4,6, . . . ,p-1$ when taken modulo $p$. The number of these can be seen to be $(p-1)/2$, so the number greater than $p/2$ is clearly $\left\lfloor{(p+1)/4}\right\rfloor$. If we say $r_j$ are the residues greater than $p/2$, and $s_i$ those less than $p/2$, with $n$ being the number of $r_j$ and $k=(p-1)/2-n$ being the number of $s_i$, then we wish to consider the following product: $$(p-r_1)(p-r_2) \cdots (p-r_n)s_1s_2 \cdots s_k$$ Now, the numbers $p-r_j$ and $s_j$ are all distinct. If they were not then we would have: $$p-r_j=s_i \,\Rightarrow \, p=r_j+s_i \,\Rightarrow \, 2|p$$ (2 would have to divide $p$ since all the integers under consideration are even.) Since $p\neq 2$, this is impossible; so we have a distinct set of integers. There are $(p-1)/2$ of them, and all are less than $p/2$. So they must be $1,2, . . . ,(p-1)/2$. Therefore: $$\eqalign{ (p-r_1)(p-r_2) \dots (p-r_n)s_1s_2 \dots s_k &= 1\cdot2\dots{p-1\over2}\cr (-r_1)(-r_2)\dots (-r_n)s_1s_2 \dots s_k &\equiv 1\cdot2\dots{p-1\over2} \pmod p\cr r_1r_2\dots r_ns_1s_2 \dots s_k &\equiv (-1)^n\cdot1\cdot2\dots{p-1\over2} \pmod p\cr }$$ However, remember that the product of all the $r_j$ and $s_i$ is simply the original product $2\cdot4\dots(p-1)$: $$2^{p-1\over2} \cdot 1\cdot2\dots{p-1\over2} \equiv r_1r_2\dots r_ns_1s_2\dots s_k \equiv (-1)^n \cdot 1\cdot2\dots{p-1\over2} \pmod p $$ so $$(-1)^n\equiv 2^{p-1\over2} \pmod p$$ But earlier we noticed that $n={\left\lfloor{p+1\over4}\right\rfloor}$; so, as required, $2^{p-1\over 2}\equiv(-1)^{p+1\over4}\pmod p$. The congruence we had to solve was $$2^{p-1\over2}(-1)^{p-1\over2} \equiv1\pmod p,$$ and we now see that this is equivalent to $$(-1)^{\left\lfloor{p+1\over4}\right\rfloor}(-1)^{p-1\over2} \equiv1\pmod p.$$ This means that we have to determine when ${\left\lfloor{(p+1)/4}\right\rfloor}+(p-1)/2$ is even, in the knowledge that $p$ is odd. We consider the following to be possible forms of $p$: $$p\equiv -3,-1,1,3 \pmod 8$$ Upon substitution we see that the following forms of prime are the only solutions which will work, and they will always have solutions: $$p\equiv \hbox{1 or 3}\pmod 8$$ This produces the required result for the Theorem. (Again, what we have proved is that the congruence has a solution only if $p\equiv \hbox{1 or 3}\pmod 8$. And again, it's possible, but harder to prove, if .)

Theorem 3:

A prime $p$ can be represented in the form $a^2+b^2$ if the congruence $x^2\equiv-1\pmod p$ is solvable.

Proof:

Consider pairs of integers $(m,n)$ and let $R=\left\lfloor\sqrt p\right\rfloor$. Hence we have $R< \sqrt{p}p$ different pairs. Now look at the $r$ for which $$m+nx\equiv r\pmod p$$ There are more pairs under consideration than distinct residues, hence by the pigeonhole principle we have: $$\eqalign{ &m_1 + n_1x \equiv m_2+n_2x \pmod p\cr \Rightarrow \; &m_1-m_2 \equiv -x(n_1-n_2) \pmod p\cr \Rightarrow \; &(m_1-m_2)^2 \equiv x^2(n_1-n_2)^2 \equiv -(n_1-n_2)^2 \pmod p \quad\hbox{since $x^2\equiv 1$}\cr \Rightarrow \; &(m_1-m_2)^2+(n_1-n_2)^2\equiv 0 \pmod p\cr }$$ But we know from our earlier statements that $$(m_1-m_2)^2+(n_1-n_2)^2 \leq 2R^2 < 2p.$$ Also, since the pairs above are distinct these squares cannot both be 0, hence we have $$0 < (m_1-m_2)^2+(n_1-n_2)^2 < 2p$$ and so $(m_1-m_2)^2+(n_1-n_2)^2=p$. This completes the theorem.

Theorem 4:

A prime $p$ can be represented in the form $a^2+2b^2$ if the congruence $x^2\equiv-2\pmod p$ is solvable.

Proof:

We employ an almost identical proof for this theorem as we did for the last one. Consider pairs of integers $(m,n)$ and let $R=\lfloor \sqrt p \rfloor$. Hence we have $R< \sqrt{p}p$ different pairs. Now look at the $r$ for which $$m+nx\equiv r\pmod p$$ There are more pairs under consideration than distinct residues, hence by the pigeonhole principle we have: $$\eqalign{ &m_1 + n_1x \equiv m_2+n_2x \pmod p\cr \Rightarrow \; &m_1-m_2 \equiv -x(n_1-n_2) \pmod p\cr \Rightarrow \; &(m_1-m_2)^2 \equiv x^2(n_1-n_2)^2 \equiv -2(n_1-n_2)^2 \pmod p \quad\hbox{since $x^2\equiv -2$}\cr \Rightarrow \; &(m_1-m_2)^2+2(n_1-n_2)^2\equiv 0 \pmod p\cr }$$ But we know from our earlier statements that $$(m_1-m_2)^2+2(n_1-n_2)^2 \leq 3R^2 < 3p$$ Also, since the pairs above are distinct these squares cannot both be 0, hence we have $$0 < (m_1-m_2)^2+(n_1-n_2)^2 < 3p$$ and so $(m_1-m_2)^2+(n_1-n_2)^2$ is either $p$ or $2p$. Suppose $p$ is an odd prime such that $a^2+b^2=2p$, then $a$ is obviously even. If $a$ is even then 4 divides $a^2$, so 4 cannot divide $2b^2$, so $b$ is odd. But then we have $$2a^2+4b^2 = 4p \,\Rightarrow \, b^2 + 2\left({a\over2}\right)^2 = p.$$ Thus we conclude that any odd prime satisfying the stated congruence can be expressed in the stated form, which completes the theorem since clearly it's true for $p=2$.

Theorem 5:

The product of any two numbers of the form $a^2+b^2$ can also be written in that form.}

Proof:

$$(a^2+b^2)(m^2+n^2) = (am-bn)^2 + (an+bm)^2$$ This algebraic identity proves the Theorem.

Theorem 6:

The product of any two numbers of the form $a^2+2b^2$ can also be written in that form.

Proof:

$$(a^2+2b^2)(m^2+2n^2) = (am+2bn)^2 + 2(an-bm)^2$$ This algebraic identity proves the Theorem.

Observe that 2 can be written as the sum of squares, and also note the following identity: $$2(a^2+2b^2) = (2b)^2+2a^2$$ and it can be expressed as $$2(a^2+b^2) = (a-b)^2 + (a+b)^2$$ wtf? The purpose of establishing the above theorems is to try to put forward a coherent theory on the sums of three squares. I would suggest that all numbers except those of the form $4^\alpha(7+8k)$ can be represented as the sum of three or less squares. Combining Theorems 2, 4 and 6 we observe that any number whose canonical factoring takes the form $$2^\alpha\prod q^\beta\prod p^\gamma$$ where $q$ and $p$ are of the form 1 and 3 mod 8 respectively can be represented as the sum of three squares. Similarly any number with the canonical factoring of the form $$2^\alpha\prod q^\beta\prod p^\gamma$$ where $q$ and $p$ are of the form 1 and 5 mod 8 respectively can be represented as the sum of three squares. Obviously I have not shown that all numbers except those of the form $4^\alpha(7+8k)$ can be represented as the sum of three squares, but I would like to put that to anyone who is interested. Also it would be interesting to know if the sum was unique or otherwise. I hope that the above has been of interest and you will be spurred to response!