# Sum of three squares: need to check the expressions with the lower powers of $4$.

It is a well-known theorem that a positive integer cannot be expressed as a sum of three squares iff. it is of the form $4^n(8m+7)$ for some non-negative integers $m$ and $n$.

E.g. $136=2^3(17)=4^1[8(4)+2]$ and $=4^0[8(17)+0]$, so 136 is expressible as the sum of three squares.

My course materials state that it is necessary to check only the highest power of 4 (i.e. the second case $4^0[8(17)+0]$ is redundant). But why this is so?

Thank you.

This is so because if you take a power of $4$ inside the parentheses, the thing added to $8m$ will be even-either $0$ or $4$ and will not be $7$.

• I don't think I've ever tied to the second before. – Will Jagy Nov 2 '12 at 17:27
• @WillJagy: and our answers are almost orthogonal. I hope the combination helps OP. – Ross Millikan Nov 2 '12 at 17:32
• @Ryan: If $4^n$ is the highest power dividing $k$, write $k=4^n(8m+r)$ for $1 \ le r \le 7$. Then $k = 4^{n-1}(8(4m)+4r)$. The result of taking $\frac k{4^{n-1}} \pmod 8$ cannot be $7$ – Ross Millikan Nov 2 '12 at 17:49
• I finally read your answer properly and have figured it out. Thanks! – Ryan Nov 2 '12 at 22:54

I'm having some trouble following your thinking, but the simple truth is that, if $$x^2 + y^2 + z^2 = 4n,$$ then $x,y,z$ must all be even, so we get an integral expression $$\left( \frac{x}{2} \right)^2 + \left( \frac{y}{2} \right)^2 + \left( \frac{z}{2} \right)^2 = n.$$ That is, $n$ is the sum of three squares if and only if $4n$ is the sum of three squares. Furthermore, among numbers that are not divisible by $4,$ those that are $1,2,3,5,6 \pmod 8$ are expressible as the sum of three squares, while those that are $7 \pmod 8$ are not. The difficult theorem is the part about $1,2,3,5,6 \pmod 8$ succeeding.

So the way I would word the thing, keep dividing out by $4$ until the number is no longer divisible by $4.$ Check that number to see whether you get $1,2,3,5,6 \pmod 8$ or $7 \pmod 8.$

Maybe this example will show something: instead of 136 take 240, as in $$240=4^0[8(30)+0] = 4^1[8(7)+4] = 4^2[8(1)+7].$$ Either of the expressions with $4^0$ or $4^1$ gives you a misleading impression, since $240$ is not the sum of three squares.

• Thanks Will. The problem is, if the expression with the highest power of 4 doesn't indicate that the integer is inexpressible as the sum of three squares, I still can't convince myself that this is conclusive that the integer is expressible as the sum of three squares. Which boils down to this problem: why is it that $x\not\equiv7\implies4^nx\not\equiv7 (\mod 8)$? – Ryan Nov 2 '12 at 17:50
• My best advice is for you to get on a computer, run a three variable loop and see what numbers up to $1000$ are the sum of three squares, where squares include $0.$ Make a separate list of all the numbers up to $1000$ that are not the sum of three squares. Subject both lists to various tests you might have in mind and see what happens. – Will Jagy Nov 2 '12 at 17:57
• @Ryan: For any value of $x$ (no matter if $x\equiv 7\pmod 8$ or not), you have $4^n x\equiv 0\pmod 8$ or $4^n x\equiv 4\pmod 8$. In fact, if $n\ge 2$, you can only have $4^nx\equiv 0\pmod 8$ because already $4^2=16$ is a multiple of $8$. – Hagen von Eitzen Nov 2 '12 at 21:45

Given a positive integer of the form $4^n [8m_1 + R_1]$ where $n$ is a non-negative integer, we can (if $n$ isn't $0$) re-express it so that $4$ takes on a lower power: $4^{n-k} [8(4^km_1) +R_2]$ where $R_2 \equiv 4^kR_1 (\mod 8)$.

Working$\mod 8$:

If $k > 1$, then $R_1 \equiv R_2$.

If $k = 1$, then $R_2 \equiv 0$ or $4$ (depending on the value of $R_1$).

Hence, given a positive integer of the form $4^n [8m_1 + R_1]$ where $n$ takes on its greatest value and where $R_1$ is not $7$, and we re-express it so that $n$ takes on a lower value, then $R_2$ will also not be $7$.

So, to ascertain whether a given integer is a sum of three squares, we need only apply the stated theorem on its expression containing the highest power of 4.