0
$\begingroup$

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.

3 Answers 3

0

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.

3

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.

  • 0
    @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$.2012-11-02
3

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$.

  • 0
    I finally read your answer properly and have figured it out. Thanks!2012-11-02