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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't think I've ever tied to the second before. $\endgroup$ – Will Jagy Nov 2 '12 at 17:27
  • $\begingroup$ @WillJagy: and our answers are almost orthogonal. I hope the combination helps OP. $\endgroup$ – Ross Millikan Nov 2 '12 at 17:32
  • $\begingroup$ @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$ $\endgroup$ – Ross Millikan Nov 2 '12 at 17:49
  • $\begingroup$ I finally read your answer properly and have figured it out. Thanks! $\endgroup$ – Ryan Nov 2 '12 at 22:54
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$? $\endgroup$ – Ryan Nov 2 '12 at 17:50
  • $\begingroup$ 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. $\endgroup$ – Will Jagy Nov 2 '12 at 17:57
  • $\begingroup$ @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$. $\endgroup$ – Hagen von Eitzen Nov 2 '12 at 21:45
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.