Age
16 to 18
| Article by
Tom Sanders
| Published

More sums of squares



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=x2+y2+z2. 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. 3odd numbers:x2+y2+z23(mod4)2 oddnumbers:x2+y2+z22(mod4)1 oddnumber:x2+y2+z21(mod4)0 oddnumbers:x2+y2+z20(mod4)
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)p12(x2)p12xp1(modp) However, we know by Fermat's Little Theorem that xp11(modp)(1)p12(modp) However, since $p> 2$ we have 11(modp) 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)p122p12(1)p121(modp) 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: 2p12(1)p+14(modp) 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: (pr1)(pr2)(prn)s1s2sk Now, the numbers $p-r_j$ and $s_j$ are all distinct. If they were not then we would have: prj=sip=rj+si2|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: (pr1)(pr2)(prn)s1s2sk=12p12(r1)(r2)(rn)s1s2sk12p12(modp)r1r2rns1s2sk(1)n12p12(modp) However, remember that the product of all the $r_j$ and $s_i$ is simply the original product $2\cdot4\dots(p-1)$: 2p1212p12r1r2rns1s2sk(1)n12p12(modp) so (1)n2p12(modp) 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 2p12(1)p121(modp), and we now see that this is equivalent to (1)p+14(1)p121(modp). 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$: p3,1,1,3(mod8) Upon substitution we see that the following forms of prime are the only solutions which will work, and they will always have solutions: p1or 3(mod8) 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+nxr(modp) There are more pairs under consideration than distinct residues, hence by the pigeonhole principle we have: m1+n1xm2+n2x(modp)m1m2x(n1n2)(modp)(m1m2)2x2(n1n2)2(n1n2)2(modp)since x21(m1m2)2+(n1n2)20(modp) But we know from our earlier statements that (m1m2)2+(n1n2)22R2<2p. Also, since the pairs above are distinct these squares cannot both be 0, hence we have 0<(m1m2)2+(n1n2)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+nxr(modp) There are more pairs under consideration than distinct residues, hence by the pigeonhole principle we have: m1+n1xm2+n2x(modp)m1m2x(n1n2)(modp)(m1m2)2x2(n1n2)22(n1n2)2(modp)since x22(m1m2)2+2(n1n2)20(modp) But we know from our earlier statements that (m1m2)2+2(n1n2)23R2<3p Also, since the pairs above are distinct these squares cannot both be 0, hence we have 0<(m1m2)2+(n1n2)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 2a2+4b2=4pb2+2(a2)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:

(a2+b2)(m2+n2)=(ambn)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:

(a2+2b2)(m2+2n2)=(am+2bn)2+2(anbm)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(a2+2b2)=(2b)2+2a2 and it can be expressed as 2(a2+b2)=(ab)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αqβpγ 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αqβpγ 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!