# More Sums of Squares

##### Age 16 to 18

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!